4 papers · 1 filter
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 -…
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…
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…