Showing cs.DMShow all
2 papers · 1 filter
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…
cs.DM2025
On classes of bounded tree rank, their interpretations, and efficient sparsification
Jakub Gajarský, Rose McCarty
Graph classes of bounded tree rank were introduced recently in the context of the model checking problem for first-order logic of graphs. These graph classes are a common generaliz…