Daligault–Rao–Thomassé conjecture on well-quasi-ordering and clique-width
A graph class is hereditary if it is closed under taking induced subgraphs. Such a class is finitely defined if it can be characterised by a finite set of minimal forbidden induced subgraphs. A class is well-quasi-ordered by the induced subgraph relation if it contains no infinite antichain under that relation. The clique-width of a graph is the minimum number of labels needed to construct it using the standard clique-width operations.
Daligault–Rao–Thomassé conjecture. If a finitely defined hereditary class of graphs is well-quasi-ordered by the induced subgraph relation, then has bounded clique-width.
A negative answer is known for hereditary classes whose sets of minimal forbidden induced subgraphs are infinite, but the finitely defined case remains open according to the source.
References
- Konrad K. Dabrowski, Vadim V. Lozin and Daniël Paulusma, “Clique-width and Well-Quasi-Ordering of Triangle-Free Graph Classes”, arXiv:1711.08837 (2017).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.