43 problems

Flip-width subpolynomial collapse conjecture. The following conditions are equivalent:

Let $\mathcal{P}$ denote the class of paths, let $\mathcal{T}_n$ denote the class of rooted trees of height at most $n$, and let $\sqsupseteq_\mathrm{FO}$ denote the first-order tr…

Let $\mathcal{C}$ be a class of graphs, let $\mathcal{P}$ denote the class of paths, and let $\sqsupseteq_\mathrm{FO}$ denote the first-order transduction quasiorder. A graph class…

Let $d\geq 2$, and let $\mathcal{G}$ be a $K_{1,d}$-free graph class of twin-width at most $3$. Twin-width conjecture. Does $\mathcal{G}$ have bounded tree-independence number? The…

Let $d\geq 2$, and let $\mathcal{G}$ be a $K_{1,d}$-free graph class. Sim-width conjecture. If $\mathcal{G}$ has bounded sim-width, then $\mathcal{G}$ has bounded tree-independence…

Let $d\geq 2$ be an integer, let $G$ be a $K_{1,d}$-free graph, and let $f$ be a polynomial. Polynomial-bound conjecture. There is a polynomial $f$ such that, whenever $G$ does not…

Let $d$ be a positive integer and let $\mathcal{G}$ be a hereditary $K_{1,d}$-free graph class. Dallard et al.'s conjecture. The class $\mathcal{G}$ has bounded tree-independence n…

Let $\mathcal{G}_k$ be the graph class defined in the paper for each $k\in\mathbb{N}$. Hierarchy properness conjecture. For each $k\in\mathbb{N}$, the inclusion … is proper. The co…

For a family $\mathcal{F}$ of graphs, a graph $G$ is $\mathcal{F}$-free if no induced subgraph of $G$ is isomorphic to a graph in $\mathcal{F}$. Let $P_r$ be the path with $r$ vert…

Let $\mathcal{C}$ be a hereditary class of finite graphs. Lopez's path-transduction conjecture. If $\mathcal{C}$ is not $2$-well-quasi-ordered, then $\mathcal{C}$ existentially tra…

A wheel is a graph consisting of an induced cycle of length at least $4$ and one additional vertex adjacent to at least three vertices on the cycle. A graph class is Burling-contro…

A graph class is Burling-controlled when its chromatic complexity is controlled by the Burling graphs, as defined in the source. An induced subdivision of a graph $F$ is a subdivis…

For a positive integer $s$, a graph is $K_{s,s}$-free if it contains no subgraph isomorphic to $K_{s,s}$. Linear pivot-minor degree-boundedness conjecture. For each bipartite graph…

Kanté and Kwon's conjecture. A vertex-minor-closed class of graphs has bounded linear rank-width if and only if it does not contain some tree.

Let $r\geq 4$. A graph is $C_{2r}$-subgraph-free if it contains no subgraph isomorphic to the cycle $C_{2r}$. The diameter of a graph is the maximum distance between two vertices.…

Bounded tree-independence conjecture. For any two positive integers $k$ and $t$, the class of $\{P_k,K_{t,t}\}$-free graphs has bounded tree-independence number.

A family of unbounded treewidth is a family of graphs whose treewidth is unbounded, and it is essential when its hereditary closure is a minimal hereditary class of unbounded treew…

A hereditary class is a graph class closed under induced subgraphs, and twin-width is the graph parameter measuring the minimum contraction complexity under sequences of vertex ide…

Transduction preservation conjecture. The property of being a perturbation of a class of bounded expression-stable $\ca P^\circ$-clique-width is preserved under taking first-order…

Let $\mathcal{G}$ be a natural graph class, and let $k$ be a positive integer. For a graph $G$ with a $k$-assignment $L$, let $\mathcal{C}_L(G)$ be the graph of proper $L$-coloring…

Let $\mathcal{G}$ be a hereditary graph class. A graph class is $(\mathsf{tw},\omega)$-bounded if its treewidth is bounded by a function of its clique number, and it has bounded tr…

Let $C$ be a hereditary graph class. Bounded-rank alternation conjecture. The class $C$ has bounded rank if and only if there is $kinmathbb{N}$ such that every first-order fo…

Let $C$ be a hereditary graph class. For $dinmathbb{N}$, let $Td$ denote the class of all trees of depth $d$. Pilipczuk–Toruńczyk's rank conjecture. The class $C$ has elemen…

A hole is an induced cycle on four or more vertices. A t-clock is a clock consisting of a hole $C$ and a vertex $v$ such that there are two neighbours $x,y\in V(C)$ of $v$ where th…

Le's induced-path conjecture. There is a constant $c$ such that every $\mathcal{O}_2$-free $n$-vertex graph has at most $n^c$ distinct induced paths.