{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-12","reactions":{}}