ProbXiv
Explorersign in
Problem archiveProblem record

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

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.