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

From papers

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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

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).

Solutions 0

No solutions have been posted yet.