Showing 2025Show all
3 papers · 1 filter
cs.LO2025
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…
math.CO2025
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…
cs.LO2025
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…