8 papers
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…
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 -…
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…
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…