3 papers
cs.DM2026
Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes
Jan Dreier, Nikolas Mählmann, Rose McCarty +2
Monadic dependence is a proposed structural dividing line for fixed-parameter tractability of first-order model checking on hereditary graph classes. A graph class is \emph{monadic…
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 -…
cs.LO2025
Elementary first-order model checking for sparse graphs
Jakub Gajarský, MichaÅ Pilipczuk, Marek SokoÅowski +2
It is known that for subgraph-closed graph classes the first-order model checking problem is fixed-parameter tractable if and only if the class is nowhere dense [Grohe, Kreutzer, S…