12 problems

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…

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 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}$.

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…

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…