Hereditary pattern-free classes are not always 2-wqo

2026/07/24 by Robert Brignall · 1 citation
#math.CO #cs.DM

paper · pdf

Abstract

A pattern is a fundamental object used in the proof of Duron, Mählmann and Toruńczyk to show that hereditary 2-wqo graph classes have bounded clique-width. We answer a question in that paper by exhibiting a pattern-free hereditary graph class that is not 2-wqo.

Citations

• Hereditary 2-WQO Graph Classes Have Bounded Clique-Width
• A counterexample regarding labelled well-quasi-ordering

Cited by

• Hereditary 2-WQO Graph Classes Have Bounded Clique-Width

Related

• Hereditary 2-WQO Graph Classes Have Bounded Clique-Width
• Clique-width and Well-Quasi-Ordering of Triangle-Free Graph Classes
• Linear Clique-Width for Hereditary Classes of Cographs
• Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation
• Hereditary Graph Classes: When the Complexities of Colouring and Clique Cover Coincide