Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2603.13522 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908885484306432 |
|---|---|
| author | English, Sean Swan, London |
| author_facet | English, Sean Swan, London |
| contents | The domatic game with pallete size $k$ is a $2$-player game played on a graph $G$ recently introduced by Hartnell and Rall. Players Alice and Bob take turns choosing an uncolored vertex from $G$, and coloring it a color from $\{1,2,\dots,k\}$. The game ends once all vertices in $G$ have been assigned a color. Alice wins if all $k$ colors induce a dominating set of $G$, and otherwise Bob wins. The domatic game number, $\operatorname{dom_g}(G,X)$ is the the largest pallete size $k$ such that Alice wins the domatic game when player $X$ goes first (where $X$ is either Alice or Bob).
We prove for any graph $G$ of order $n$,
\[
\operatorname{dom_g}(G,X)=Ω\left(\frac{δ(G)}{\log n}\right).
\]
In addition, we show that for any $k$ there exists a graph $G$ with minimum degree $δ(G)=k$ and $\operatorname{dom_g}(G,X)=1$, and there exists a graph $G'$ with $\operatorname{dom_g}(G',X)=1$ while having (non-game) domatic number $\operatorname{dom}(G')=k$. We explore how the domatic game number changes when changing who goes first, and when considering subgraphs of $G$. We also introduce a score variant of the domatic game, and use this to get bounds on the original domatic game. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_13522 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Domatic Game English, Sean Swan, London Combinatorics The domatic game with pallete size $k$ is a $2$-player game played on a graph $G$ recently introduced by Hartnell and Rall. Players Alice and Bob take turns choosing an uncolored vertex from $G$, and coloring it a color from $\{1,2,\dots,k\}$. The game ends once all vertices in $G$ have been assigned a color. Alice wins if all $k$ colors induce a dominating set of $G$, and otherwise Bob wins. The domatic game number, $\operatorname{dom_g}(G,X)$ is the the largest pallete size $k$ such that Alice wins the domatic game when player $X$ goes first (where $X$ is either Alice or Bob). We prove for any graph $G$ of order $n$, \[ \operatorname{dom_g}(G,X)=Ω\left(\frac{δ(G)}{\log n}\right). \] In addition, we show that for any $k$ there exists a graph $G$ with minimum degree $δ(G)=k$ and $\operatorname{dom_g}(G,X)=1$, and there exists a graph $G'$ with $\operatorname{dom_g}(G',X)=1$ while having (non-game) domatic number $\operatorname{dom}(G')=k$. We explore how the domatic game number changes when changing who goes first, and when considering subgraphs of $G$. We also introduce a score variant of the domatic game, and use this to get bounds on the original domatic game. |
| title | On the Domatic Game |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.13522 |