Daligault–Rao–Thomassé conjecture on well-quasi-ordering and clique-width
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.