Showing cs.LOShow all
2 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…
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…