Lozin–Razgon–Zamaraev's finite-definition conjecture for induced-subgraph well-quasi-ordering

From papers

Let G\mathcal{G} be a hereditary graph class defined by a finite set of forbidden induced subgraphs. A graph is labelled by assigning to each vertex an element of a quasi-order (W,)(W,\leq). The class G\mathcal{G} is well-quasi-ordered by the labelled induced subgraph relation if, for every well-quasi-order (W,)(W,\leq), it contains no infinite antichain of labelled graphs under that relation. Ordinary well-quasi-ordering by the induced subgraph relation is defined analogously without vertex labels.

Lozin–Razgon–Zamaraev's labelled induced-subgraph conjecture. If G\mathcal{G} is defined by a finite set of forbidden induced subgraphs, then G\mathcal{G} is well-quasi-ordered by the induced subgraph relation if and only if it is well-quasi-ordered by the labelled induced subgraph relation.

Labelled induced-subgraph well-quasi-ordering always implies ordinary induced-subgraph well-quasi-ordering, and Daligault, Rao and Thomassé proved that labelled well-quasi-ordering forces finite definability. The conjecture proposes that finite definability makes the converse implication hold; the supplied text does not establish its resolution.

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, Matthew Johnson and Daniël Paulusma, “Clique-Width for Hereditary Graph Classes”, arXiv:1901.00335 (2019).

Solutions 0

No solutions have been posted yet.