Daligault–Rao–Thomassé conjecture on well-quasi-ordering and clique-width
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.
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
Sign in to submit a solution.
No solutions have been posted yet.