A Note on Constructive Canonical Splitter Strategies in Nowhere Dense Graph Classes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910168001806336 |
|---|---|
| author | Fuchser, Janne Mählmann, Nikolas Siebertz, Sebastian |
| author_facet | Fuchser, Janne Mählmann, Nikolas Siebertz, Sebastian |
| contents | The radius-$r$ splitter game is played on a graph $G$ between two players: Splitter and Connector. In each round, Connector selects a vertex $v$, and the current game arena is restricted to the radius-$r$ neighborhood of $v$. Then Splitter removes a vertex from this restricted subgraph. The game ends, and Splitter wins, when the arena becomes empty. Splitter aims to end the game as quickly as possible, while Connector tries to prolong it for as long as possible. The splitter game was introduced by Grohe, Kreutzer and Siebertz to characterize nowhere dense graph classes. They showed that a class $\mathscr{C}$ of graphs is nowhere dense if and only if for every radius $r$ there exists a number $k$ such that Splitter has a strategy on every $G\in \mathscr{C}$ to win the radius-$r$ splitter game in at most $k$ rounds. It was recently proved by Ohlmann et al. that for every nowhere dense class $\mathscr{C}$ and every radius $r$ there are only a bounded number of possible Splitter moves that are progressing, that is, moves that lead to an arena where Splitter can win in one less round. The proof of Ohlmann et al. is based on the compactness theorem and does not give a constructive bound on the number of progressing moves. In this work, we give a simple constructive proof, showing that if Splitter can force a win in the radius-$r$ game in $k$ rounds, then there are at most $(2r+1)^{\,2^{k-1}-1}$ progressing moves. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10062 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Note on Constructive Canonical Splitter Strategies in Nowhere Dense Graph Classes Fuchser, Janne Mählmann, Nikolas Siebertz, Sebastian Logic in Computer Science Discrete Mathematics Logic The radius-$r$ splitter game is played on a graph $G$ between two players: Splitter and Connector. In each round, Connector selects a vertex $v$, and the current game arena is restricted to the radius-$r$ neighborhood of $v$. Then Splitter removes a vertex from this restricted subgraph. The game ends, and Splitter wins, when the arena becomes empty. Splitter aims to end the game as quickly as possible, while Connector tries to prolong it for as long as possible. The splitter game was introduced by Grohe, Kreutzer and Siebertz to characterize nowhere dense graph classes. They showed that a class $\mathscr{C}$ of graphs is nowhere dense if and only if for every radius $r$ there exists a number $k$ such that Splitter has a strategy on every $G\in \mathscr{C}$ to win the radius-$r$ splitter game in at most $k$ rounds. It was recently proved by Ohlmann et al. that for every nowhere dense class $\mathscr{C}$ and every radius $r$ there are only a bounded number of possible Splitter moves that are progressing, that is, moves that lead to an arena where Splitter can win in one less round. The proof of Ohlmann et al. is based on the compactness theorem and does not give a constructive bound on the number of progressing moves. In this work, we give a simple constructive proof, showing that if Splitter can force a win in the radius-$r$ game in $k$ rounds, then there are at most $(2r+1)^{\,2^{k-1}-1}$ progressing moves. |
| title | A Note on Constructive Canonical Splitter Strategies in Nowhere Dense Graph Classes |
| topic | Logic in Computer Science Discrete Mathematics Logic |
| url | https://arxiv.org/abs/2509.10062 |