Korpelainen–Lozin–Razgon conjecture on labelled well-quasi-ordering of graph classes

Let a graph class be well-quasi-ordered (wqo) by the induced subgraph relation if it contains no infinite antichain under that relation, and let it be labelled well-quasi-ordered (lwqo) if the analogous property holds for graphs whose vertices are labelled by elements of every wqo label set. A graph class is defined by finitely many minimal forbidden induced subgraphs when its set of minimal graphs excluded as induced subgraphs is finite.

Korpelainen–Lozin–Razgon conjecture. A class of graphs which is wqo by the induced subgraph relation is lwqo if and only if it is defined by finitely many minimal forbidden induced subgraphs.

Every lwqo graph class is wqo and defined by finitely many minimal forbidden induced subgraphs, so the conjecture asserts the converse implication as well. The paper disproves this conjecture by constructing a class of permutation graphs that is wqo and has finitely many minimal forbidden induced subgraphs but is not lwqo.