23 problems

Let $\mathscr C$ be a class of tree-ordered weakly sparse graphs (TOWS graphs). A dense analogue of a weakly sparse class property is obtained by requiring every weakly sparse tran…

Daligault–Rao–Thomassé conjecture. If a finitely defined hereditary class of graphs $\mathcal{G}$ is well-quasi-ordered by the induced subgraph relation, then $\mathcal{G}$ has bou…

Let $X$ be a minimal hereditary class of graphs of unbounded clique-width. A canonical infinite coloured antichain is the canonical infinite coloured antichain associated with such…

Bonnet–Duron's conjecture. Every class of graphs with bounded stretch-width has clique-width at most logarithmic in the number of vertices; equivalently, there is a constant $c$ su…

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. The bounded clique-width conjecture. If $\mathcal{C}$ is $2$-well-quasi-ordered, then $\mathcal{C}$ has bounded clique-wid…

Let $G$ be a graph and let ${\cal P}$ be a monotone partition of $V(G)$ into cliques. Assume that the box graph $b(G;{\cal P})$ is a chordless cycle. The logarithmic cyclic-box con…

Let $G$ be a graph, and let ${\cal P}=(A_1,\ldots,A_k)$ be a monotone partition of $V(G)$ into cliques. The box graph $b(G;{\cal P})$ has a chordless cycle…

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…

Perfect-or-bounded-clique-width conjecture. One of the following holds:

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…

Expression-stability conjecture. There is a function $g:\mathbb{N}\to\mathbb{N}$ such that each $(\ca Q_r^\circ,\ell)$-expression constructed in the proof of the transduction lemma…

Let $\mathcal{C}$ be a stable class of graphs of twin-width at most $2$. Stable twin-width 2 conjecture. Then $\mathcal{C}$ has bounded clique-width. This conjecture is the correct…

Let $\mathcal{C}$ be a class of graphs of twin-width at most $2$. Bounded clique-width conjecture. Then $\mathcal{C}$ has bounded clique-width. This unrestricted version is false,…

Let $\mathcal C$ be a class of graphs of bounded stretch-width. For an $n$-vertex graph $G\in\mathcal C$, let the clique-width of $G$ be the minimum number of labels needed to cons…

Characterisation conjecture. The hereditary graph class $\mathcal{G}^\delta$ is minimal of unbounded clique-width if and only if $\delta \in \Delta_{min}$.

Let an infinite word over the alphabet $\{0,1,2\}$ define a hereditary bipartite graph class by taking the finite induced subgraphs of the associated infinite graph whose vertices…

A graph class is 2-wqo when the set of its graphs labeled by a 2-element antichain is well-quasi-ordered. Daligault–Rao–Thomassé's conjecture. Every 2-wqo class of graphs has bound…

Lozin–Razgon–Zamaraev's conjecture. If a finitely defined hereditary graph class $\mathcal{G}$ is well-quasi-ordered by the induced subgraph relation, then $\mathcal{G}$ has bounde…

Let $X$ be a hereditary class of graphs. A coloured induced subgraph is a graph embedded as an induced subgraph in a way that respects vertex colours, and an infinite coloured anti…

Let $\alpha$ be an infinite word over the alphabet $\\{0,1,2\\}$. An infinite word is almost periodic if every factor $\beta$ of $\alpha$ occurs in every sufficiently long factor o…

Let a minimal hereditary class of unbounded clique-width mean a hereditary graph class of unbounded clique-width whose every proper hereditary subclass has bounded clique-width. Su…

A permutation class $\mathcal{C}$ is broadly rational if every finitely based subclass of $\mathcal{C}$ has a rational generating function, and it is strongly rational if it and al…