The Normal Domination Partizan Game in Stars
Pith reviewed 2026-05-09 15:06 UTC · model grok-4.3
The pith
The winner of the normal partizan domination game on complete split graphs and star forests is fixed by any initial vertex coloring.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We determine the winner of the Normal Partizan Domination game in graphs whose components are complete split graphs, including star forests, for any initial coloring of its vertices. We also obtain partial results for complete bipartite graphs.
What carries the argument
Partizan vertex coloring into A, B, and C classes that restricts Alice to A or C and Bob to B or C, together with the domination condition on complete split graph components.
If this is right
- For every star forest the winner is computable directly from the coloring without enumerating moves.
- The same determination applies to any graph whose connected components are complete split graphs.
- Partial outcome rules extend at least to some complete bipartite graphs.
- The partizan restriction interacts with the split structure to eliminate the need for full game-tree search.
Where Pith is reading between the lines
- The explicit rules could be used to test whether similar closed-form determinations exist for other hereditary graph classes.
- If the determination is efficient it separates these graphs from the general PSPACE-hard instances by structure alone.
- One could check whether the same coloring-based analysis yields winners on small complete bipartite graphs where the paper gives only partial results.
Load-bearing premise
The input graphs must be exactly unions of complete split graphs with players obeying the strict color-based selection rules.
What would settle it
A concrete small star forest with a given A/B/C coloring together with exhaustive enumeration of legal plays that produces the opposite winner from the rule claimed in the paper.
read the original abstract
The Domination game is an impartial game on graphs, introduced in 2010, and proved PSPACE-complete in the normal variant in 2026. In this game, Alice and Bob alternately select playable vertices, where a vertex is playable if it dominates at least one vertex not dominated by the vertices selected before in the game. The game ends when the selected vertices form a dominating set. In the normal variant, the player unable to move loses. In contrast to the impartial game, the partizan game has the vertices already colored with $A$, $B$, or $C$, in such a way that Alice (resp. Bob) can only select vertices colored with $A$ (resp. $B$) or $C$. The partizan game was proved PSPACE-hard in 2026. In this paper, we determine the winner of the Normal Partizan Domination game in graphs whose components are complete split graphs, including star forests, for any initial coloring of its vertices. We also obtain partial results for complete bipartite graphs.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper determines the winner of the Normal Partizan Domination game on graphs whose components are complete split graphs (including star forests) for any initial A/B/C vertex coloring, where Alice may select A or C vertices and Bob may select B or C vertices. The analysis uses the structure of these graphs to classify outcomes under the normal play convention. Partial results are also given for complete bipartite graphs.
Significance. If the determination holds, the result supplies an explicit, case-by-case resolution for a natural and infinite family of graphs in a game previously shown to be PSPACE-hard. This supplies concrete, falsifiable predictions for star forests and complete split graphs and may serve as a base case for inductive arguments on larger graph classes.
minor comments (1)
- The title refers specifically to 'Stars' while the abstract and results cover the larger class of complete split graphs and their disjoint unions; a title change or subtitle would better match the stated scope.
Simulated Author's Rebuttal
We thank the referee for the positive summary of our results and the recommendation of minor revision. The manuscript fully determines the winner of the Normal Partizan Domination game on graphs whose components are complete split graphs (including star forests) for arbitrary initial A/B/C colorings, and provides partial results for complete bipartite graphs. We appreciate the recognition that these explicit classifications offer concrete, falsifiable outcomes for an infinite family of graphs in a PSPACE-hard game and may serve as base cases for further work.
Circularity Check
No significant circularity detected
full rationale
The paper determines the winner of the Normal Partizan Domination game on complete split graphs (including star forests) for arbitrary initial A/B/C colorings through direct combinatorial analysis of legal moves and domination options under the partizan selection rules. No parameters are fitted to data and then relabeled as predictions; no self-definitional loops appear in the game rules or graph classes; no load-bearing self-citations or uniqueness theorems imported from the authors' prior work are invoked to force the result. The derivation proceeds by exhaustive case handling on the structured components, which is self-contained and independent of the target outcome.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Standard rules of the domination game and partizan coloring as introduced in 2010 and 2026
Reference graph
Works this paper leans on
- [1]
- [2]
-
[3]
Bermond, Jean-Claude and Cosnard, Michel and Havet, Fr
-
[4]
Smash and grab: The 0 6 scoring game on graphs , journal =. 2024 , author =
work page 2024
-
[5]
Computer analysis of Sprouts with nimbers , booktitle=
Lemoine, Julien and Viennot, Simon , editor=. Computer analysis of Sprouts with nimbers , booktitle=. 2015 , pages=
work page 2015
-
[6]
Incidence, a scoring positional game on graphs , journal =. 2024 , author =
work page 2024
-
[7]
The Othello game on an n × n board is Pspace-complete , journal =. 1994 , author =
work page 1994
-
[8]
The Dots and Boxes Game: Sophisticated Child's Play , author =. 2000 , publisher =
work page 2000
-
[9]
Buchin, Kevin and Hagedoorn, Mart and Kostitsyna, Irina and van Mulken, Max , title =. MFCS-2021 , pages =. 2021 , volume =
work page 2021
-
[10]
Scoring combinatorial games: the state of play , journal =. 2015 , author =
work page 2015
- [11]
-
[12]
Contributions to the Theory of Games, Vol
Milnor, John , title =. Contributions to the Theory of Games, Vol. II , series =
-
[13]
Complexity of the game domination problem , journal =. 2016 , author =
work page 2016
-
[14]
The G-values of various games , volume=. Math. Proc. Camb. Philos. Soc. , author=. 1956 , pages=
work page 1956
-
[15]
Relationships between nondeterministic and deterministic tape complexities , journal =. 1970 , author =
work page 1970
-
[16]
Brettspiele der Völker : [Rätsel und mathematische Spiele] , author=. 1931 , publisher=
work page 1931
- [17]
-
[18]
Pawlewicz, Jakub and Hayward, Ryan B. Scalable Parallel DFPN Search. Computers and Games. 2014
work page 2014
-
[19]
Impartial geodetic building games on graphs
Benesh, Bret J and Ernst, Dana C and Meyer, Marie and Salmon, Sarah K and Sieben, Nándor. Impartial geodetic building games on graphs. Int. J. Game Theory
- [20]
- [21]
-
[22]
Martins and Nisse, Nicolas and Sampaio, Rudini M
Brosse, Caroline and Nicolas A. Martins and Nisse, Nicolas and Sampaio, Rudini M. , YEAR =. Theor. Comput. Sci. , volume =
-
[23]
Martins and Nicolas Nisse and Rudini M
Caroline Brosse and Nicolas A. Martins and Nicolas Nisse and Rudini M. Sampaio , title =. Procedia Computer Science , volume =. 2025 , eprinttype =. 2412.17668 , note =
- [24]
-
[25]
A proof of the 3/5-conjecture in the domination game , journal =. 2024 , author =
work page 2024
- [26]
-
[27]
On the Game Domination Number of Graphs with Given Minimum Degree , journal =. 2015 , author =
work page 2015
- [28]
-
[29]
Kinnersley, William B. and West, Douglas B. and Zamani, Reza , title =. SIAM J. Discrete Math. , volume =
-
[30]
Domination Game and an Imagination Strategy , journal =
Bre. Domination Game and an Imagination Strategy , journal =
-
[31]
Theory of Combinatorial Games in Graphs , author=. 2026 , publisher=
work page 2026
- [32]
- [33]
-
[34]
Geometric and Functional Analysis , volume =
William Timothy Gowers , title =. Geometric and Functional Analysis , volume =
- [35]
-
[36]
Michal Kouril and Jerome L. Paul , title =. Experimental Mathematics , volume =
-
[37]
Nieuw Arch.Wiskunde , pages =
- [38]
-
[39]
Erdős, Paul , title =. Bull. Amer. Math. Soc. , number =
-
[40]
Lavrov, Mikhail , title =. SIAM J. Discrete Math. , volume =
-
[41]
Neil Hindman and Eric Tressler , title =. Ars Combinatoria , volume =
- [42]
- [43]
-
[44]
Bell, George I. and Hirschberg, Daniel S. and Guerrero-García, Pablo. The minimum size required of a solitaire army. Integers. 2007
work page 2007
-
[45]
Phillips, J.B. and Slater, P.J. An introduction to graph competition independence and enclaveless parameters. Graph. Theory Notes N.Y. 2001
work page 2001
-
[46]
H. L. Bodlaender. On the complexity of some coloring games. Int. J. Found. Comput. Sci. 1991
work page 1991
-
[47]
Two-Person Cooperative Games , volume =
John Nash , journal =. Two-Person Cooperative Games , volume =
- [48]
- [49]
- [50]
- [51]
- [52]
- [53]
-
[54]
Combinatorial Games Tic-Tac-Toe Theory , author=. 2008 , publisher=
work page 2008
-
[55]
Positional Games and the Second Moment Method , journal =. 2002 , author =
work page 2002
-
[56]
Acta Mathematica Academiae Scientiarum Hungaricae , volume=
Remarks on positional games I , author=. Acta Mathematica Academiae Scientiarum Hungaricae , volume=
-
[57]
On positional games , author=. J. Comb. Theory Ser. A. , volume=
- [58]
- [59]
-
[60]
A. W. Hales and R. I. Jewett , Title =. Trans. Am. Math. Soc. , Volume =
-
[61]
Surreal Numbers: How Two Ex-students Turned on to Pure Mathematics and Found Total Happiness: a Mathematical Novelette , author=. 1974 , publisher=
work page 1974
-
[62]
Winning Ways for Your Mathematical Plays , author=. 1982 , publisher=
work page 1982
-
[63]
Combinatorics Advances , pages=
Unsolved problems in combinatorial games , author=. Combinatorics Advances , pages=. 1995 , publisher=
work page 1995
-
[64]
Conway, J. H. , address =. On numbers and games , year =. On numbers and games , isbn =
- [65]
-
[66]
Grundy, P. M. , Title =. Eureka (The Archimedeans' Journal) , Volume =
-
[67]
Nim, Game with Complete Mathematical Theory , journal =. 1901 , author =
work page 1901
- [68]
- [69]
- [70]
- [71]
-
[72]
Dourado, Mitre C. and Ponciano, Vitor S. and. On the monophonic rank of a graph , journal =. 2022 , mrnumber =
work page 2022
-
[73]
On the pathwidth of chordal graphs , author =. Discret. Appl. Math. , volume =. 1993 , publisher =
work page 1993
-
[74]
Characterizing intersection graphs of substars of a star , author =. Ars Combinatoria , volume =. 2006 , mrnumber =
work page 2006
-
[75]
Journal of the ACM (JACM) , volume =
On the hardness of approximating minimization problems , author =. Journal of the ACM (JACM) , volume =. 1994 , publisher =
work page 1994
-
[76]
Discrete & Computational Geometry , volume =
On weak -nets and the Radon number , author =. Discrete & Computational Geometry , volume =. 2020 , publisher =
work page 2020
-
[77]
Near-linear-time algorithm for the geodetic Radon number of grids , author =. Discret. Appl. Math. , volume =. 2016 , publisher =
work page 2016
-
[78]
Discrete Mathematics , volume =
On the geodetic Radon number of grids , author =. Discrete Mathematics , volume =. 2013 , publisher =
work page 2013
-
[79]
Graph minors. II. Algorithmic aspects of tree-width , author =. Journal of algorithms , volume =. 1986 , publisher =
work page 1986
-
[80]
On an estimate of the chromatic class of a p-graph , author =. Diskret analiz , volume =. 1964 , mrnumber =
work page 1964
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.