2 citations · 3 across the 6 of their papers we have counts for
4 papers · 1 filter
A Logic for Minor-Free Graph Classes: Model Checking, Dependence, and Combinatorial Reconfiguration
Nikolas Mählmann, Patrice {Ossona de Mendez}, Nicole Schirrmacher +4
We introduce \emph{sub-connectivity logic}, denoted by , an extension of first-order logic for graphs with a specified set of admissible edges. Its additional…
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 -…
Fatness and Flatness
Arnold Filtser, Hung Le, Nikolas Mählmann +2
Fat minors are the metric analog of graph minors that are tailored to the analysis of metric (edge-weighted) graphs and, more generally, metric spaces having a suitable notion of s…
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…