ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

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.