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

At least 6 years old · documented by

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.

References

Primary source

Konrad K. Dabrowski, Matthew Johnson and Daniël Paulusma, “Clique-Width for Hereditary Graph Classes”, arXiv:1901.00335 (2019).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.