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…