Daligault–Rao–Thomassé conjecture on well-quasi-ordering and clique-width

About 9 years old · traced to

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 G\mathcal{G} is well-quasi-ordered by the induced subgraph relation, then G\mathcal{G} 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

Primary source

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

Never refreshed

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.