Lozin–Razgon–Zamaraev's finite-definition conjecture for induced-subgraph well-quasi-ordering
Lozin–Razgon–Zamaraev's finite-definition conjecture for induced-subgraph well-quasi-ordering
Let 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 . The class is well-quasi-ordered by the labelled induced subgraph relation if, for every well-quasi-order , 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 is defined by a finite set of forbidden induced subgraphs, then 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
Sign in to submit a solution.
No solutions have been posted yet.