Hereditary 2-WQO Graph Classes Have Bounded Clique-Width
2026-07-12 • Discrete Mathematics
Discrete MathematicsLogic in Computer Science
AI summaryⓘ
The authors studied special graph classes called 2-WQO, where graphs labeled in two ways follow certain ordering rules. They proved that all hereditary 2-WQO graph classes have bounded clique-width, meaning these graphs can be constructed using a limited set of operations. Combining this with prior work, they confirmed Pouzet's conjecture that being 2-WQO is equivalent to being WQO for all labelings. Their proof connects deep logical properties (monadic dependence) with graph structure and uses Ramsey theory to exclude complicated substructures that would increase clique-width.
graph classwell-quasi-ordering (WQO)hereditary graph classclique-widthlabel-preserving induced subgraph embeddingPouzet's conjecturemonadic dependenceforbidden induced subgraphsRamsey theorywell-linked sets
Authors
Julien Duron, Nikolas Mählmann, Szymon Toruńczyk
Abstract
A graph class is $k$-WQO if its $k$-labeled graphs are well-quasi-ordered under label-preserving induced subgraph embeddings. We show that every hereditary graph class that is $2$-WQO has bounded clique-width. Combined with the recent result of Dumas and Lopez, this confirms a long-standing conjecture of Pouzet: A hereditary graph class is $2$-WQO if and only if it is $k$-WQO for all $k\geq 2$, if and only if it is $\forall$-WQO, that is, its labeled graphs are well-quasi-ordered for every possible well-quasi-ordered label set. Our proof builds on a recent structure/non-structure dichotomy for the model theoretic notion of monadic dependence by Dreier, Mählmann, and Toruńczyk. Through the non-structure characterization by forbidden induced subgraphs, we show that every hereditary $2$-WQO graph class is monadically dependent. Leveraging the Ramsey-theoretic structural properties provided by monadic dependence, we then establish bounded clique-width by ruling out the existence of large well-linked sets, which are the canonical obstructions for clique-width.