Showing math.COShow all
2 papers · 1 filter
math.CO2026
Hereditary 2-WQO Graph Classes Have Bounded Clique-Width
Julien Duron, Nikolas Mählmann, Szymon Toruńczyk
A graph class is -WQO if its -labeled graphs are well-quasi-ordered under label-preserving induced subgraph embeddings. We show that every hereditary graph class that is -…
math.CO2024★ 1 cited
Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk
A conjecture in algorithmic model theory predicts that the model-checking problem for first-order logic is fixed-parameter tractable on a hereditary graph class if and only if the…