65 problems

Undecidability conjecture. The following problem is undecidable:

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.

For a positive integer $t$, an (even hole, $K_t$)-free graph is a graph containing neither an even hole nor a clique $K_t$ as an induced subgraph. Logarithmic treewidth conjecture.…

Linear Ramsey–co-chromatic conjecture. A finitely defined hereditary class is of linear Ramsey numbers if and only if it has bounded co-chromatic number.

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 $H$ be a connected graph, and let $\operatorname{Forb}(H)$ denote the class of graphs with no induced subgraph isomorphic to $H$. A graph class is DOM-bounded if its graphs hav…

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…

Let $\mathcal{C}$ be a hereditary class of finite graphs. Assume the dichotomy under consideration is the alternative that $\mathcal{C}$ is not $2$-well-quasi-ordered or that its i…

Let $\mathcal{C}$ be a hereditary class of graphs of bounded clique-width. Lopez's correspondence conjecture. The class $\mathcal{C}$ is $2$-well-quasi-ordered if and only if it is…

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…

Let $\mathcal{C}$ be a hereditary class of structures. Being universally well-quasi-ordered means that, for every well-quasi-order of labels, the class of labelled structures from…

A class of graphs is self-intersection-closed if it is closed under the self-intersection operation considered in the paper, and a class is finitely-defined when it is specified by…

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…

For a graph $F$, a graph class is $2$-controlled if bounded chromatic number on radius-$2$ closed neighborhoods controls the chromatic number of every induced subgraph, via a class…

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…

Let $\mathcal C$ be a hereditary graph class. A graph class is $(\operatorname{tw},\omega)$-bounded if there is a function $f$ such that $\operatorname{tw}(G)\leq f(\omega(G))$ for…

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…

A graph class is proper vertex-minor-closed if it is closed under vertex-minors and is not the class of all graphs. It is linearly degree-bounded if there is a linear bound, in the…

Kwon–McCarty–Oum–Wollan's conjecture. Every pivot-minor-closed class of graphs has bounded rank-depth if and only if it does not contain $P_t$ or $K_t\boxslash K_t$ for some $t$.

Let $F$ be a graph with at least two cycles. A graph is $F$-subgraph-free if it contains no subgraph isomorphic to $F$, and let $\mathcal{C}$ denote the class of $F$-subgraph-free…

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.

FO model-checking conjecture. First-Order model checking is fixed-parameter tractable on $\mathscr C$ if and only if $\mathscr C$ is dependent.