7 papers
Flips and Merge-Width in Sparse Graphs
Karolina Drabik, Maël Dumas, Nikolas Mählmann +2
A flip of a graph is obtained by complementing the edge relation within a set of vertices. Flips are typically used to separate vertices in a graph, by increasing the distances bet…
The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz
A theorem of Ding, Oporowski, Oxley, and Vertigan implies that any sufficiently large twin-free graph contains a large matching, a co-matching, or a half-graph as a semi-induced su…
Existential Positive Transductions of Sparse Graphs
Nikolas Mählmann, Sebastian Siebertz
Monadic stability generalizes many tameness notions from structural graph theory such as planarity, bounded degree, bounded tree-width, and nowhere density. The sparsification conj…
A Note on Constructive Canonical Splitter Strategies in Nowhere Dense Graph Classes
Janne Fuchser, Nikolas Mählmann, Sebastian Siebertz
The radius- splitter game is played on a graph between two players: Splitter and Connector. In each round, Connector selects a vertex , and the current game arena is rest…
Separability Properties of Monadically Dependent Graph Classes
Édouard Bonnet, Samuel Braunfeld, Ioannis Eleftheriadis +5
A graph class is monadically dependent if one cannot interpret all graphs in colored graphs from using a fixed first-order interpretation. We prove that m…
Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO
Nikolas Mählmann
The graph parameter shrub-depth is a dense analog of tree-depth. We characterize classes of bounded shrub-depth by forbidden induced subgraphs. The obstructions are well-controlled…
Recursive Backdoors for SAT
Nikolas Mählmann, Sebastian Siebertz, Alexandre Vigny
A strong backdoor in a formula of propositional logic to a tractable class of formulas is a set of variables of such that every assignment of the variable…