Id: arxiv/2607.10939 Url: https://arxiv.org/abs/2607.10939 Tags: math.CO, cs.DM, cs.LO Score: 0 Title: Hereditary 2-WQO Graph Classes Have Bounded Clique-Width Domain: math.CO Source: arxiv Authors: Julien Duron, Nikolas Mählmann, Szymon Toruńczyk Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-12 Page: https://delphi.science/r/arxiv/2607.10939 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…