pith. sign in

arxiv: 2605.01259 · v1 · submitted 2026-05-02 · 🧮 math.CO · cs.DM

The Normal Domination Partizan Game in Stars

Rudini Sampaio , Edileudo Maciel M. Filho , Jefter G. Maciel Paz , Jo\~ao Marcos Brito This is my paper

Pith reviewed 2026-05-09 15:06 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords partizan domination gamenormal playcomplete split graphsstar forestsdominating setsgraph gamescolored vertices
0
0 comments X

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.

The paper establishes that in the partizan domination game Alice and Bob can only select vertices of their assigned colors or neutral ones, and the game proceeds by alternately dominating new vertices until a dominating set forms. It fully determines the winner under normal play for every possible coloring when the graph consists of complete split components, which include star forests. This provides an explicit decision procedure for these graphs even though the general version is PSPACE-hard. A sympathetic reader cares because the result turns an otherwise intractable game into one that can be resolved by inspecting the coloring and the fixed graph structure rather than searching the move tree.

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

These are editorial extensions of the paper, not claims the author makes directly.

  • 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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

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)
  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

0 responses · 0 unresolved

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

0 steps flagged

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

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard definitions of the domination game and its partizan variant from prior literature, with no free parameters, new axioms beyond domain assumptions, or invented entities.

axioms (1)
  • domain assumption Standard rules of the domination game and partizan coloring as introduced in 2010 and 2026
    The paper builds directly on these established definitions without re-deriving them.

pith-pipeline@v0.9.0 · 5496 in / 1101 out tokens · 64880 ms · 2026-05-09T15:06:08.093053+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

300 extracted references · 87 canonical work pages

  1. [1]

    HAL Inria , pages =

    Ara. HAL Inria , pages =

  2. [2]

    1975 , publisher=

    Game Theory and Politics , author=. 1975 , publisher=

    1975

  3. [3]

    Bermond, Jean-Claude and Cosnard, Michel and Havet, Fr

  4. [4]

    2024 , author =

    Smash and grab: The 0 6 scoring game on graphs , journal =. 2024 , author =

    2024

  5. [5]

    Computer analysis of Sprouts with nimbers , booktitle=

    Lemoine, Julien and Viennot, Simon , editor=. Computer analysis of Sprouts with nimbers , booktitle=. 2015 , pages=

    2015

  6. [6]

    2024 , author =

    Incidence, a scoring positional game on graphs , journal =. 2024 , author =

    2024

  7. [7]

    1994 , author =

    The Othello game on an n × n board is Pspace-complete , journal =. 1994 , author =

    1994

  8. [8]

    2000 , publisher =

    The Dots and Boxes Game: Sophisticated Child's Play , author =. 2000 , publisher =

    2000

  9. [9]

    MFCS-2021 , pages =

    Buchin, Kevin and Hagedoorn, Mart and Kostitsyna, Irina and van Mulken, Max , title =. MFCS-2021 , pages =. 2021 , volume =

    2021

  10. [10]

    2015 , author =

    Scoring combinatorial games: the state of play , journal =. 2015 , author =

    2015

  11. [11]

    1959 , author =

    Mean play of sums of positional games , journal =. 1959 , author =

    1959

  12. [12]

    Contributions to the Theory of Games, Vol

    Milnor, John , title =. Contributions to the Theory of Games, Vol. II , series =

  13. [13]

    2016 , author =

    Complexity of the game domination problem , journal =. 2016 , author =

    2016

  14. [14]

    The G-values of various games , volume=. Math. Proc. Camb. Philos. Soc. , author=. 1956 , pages=

    1956

  15. [15]

    1970 , author =

    Relationships between nondeterministic and deterministic tape complexities , journal =. 1970 , author =

    1970

  16. [16]

    1931 , publisher=

    Brettspiele der Völker : [Rätsel und mathematische Spiele] , author=. 1931 , publisher=

    1931

  17. [17]

    1981 , author =

    Hex ist Pspace-complete , journal =. 1981 , author =

    1981

  18. [18]

    Scalable Parallel DFPN Search

    Pawlewicz, Jakub and Hayward, Ryan B. Scalable Parallel DFPN Search. Computers and Games. 2014

    2014

  19. [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. [20]

    1969 , author =

    The game of SIM , journal =. 1969 , author =

    1969

  21. [21]

    2002 , author =

    Kayles and Nimbers , journal =. 2002 , author =

    2002

  22. [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. [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 =

    work page arXiv 2025

  24. [24]

    2017 , author =

    Domination game on paths and cycles , journal =. 2017 , author =

    2017

  25. [25]

    2024 , author =

    A proof of the 3/5-conjecture in the domination game , journal =. 2024 , author =

    2024

  26. [26]

    2015 , author =

    Domination game on forests , journal =. 2015 , author =

    2015

  27. [27]

    2015 , author =

    On the Game Domination Number of Graphs with Given Minimum Degree , journal =. 2015 , author =

    2015

  28. [28]

    2021 , publisher=

    Domination Games Played on Graphs , author=. 2021 , publisher=

    2021

  29. [29]

    and West, Douglas B

    Kinnersley, William B. and West, Douglas B. and Zamani, Reza , title =. SIAM J. Discrete Math. , volume =

  30. [30]

    Domination Game and an Imagination Strategy , journal =

    Bre. Domination Game and an Imagination Strategy , journal =

  31. [31]

    2026 , publisher=

    Theory of Combinatorial Games in Graphs , author=. 2026 , publisher=

    2026

  32. [32]

    2019 , publisher=

    Hex: The Full Story , author=. 2019 , publisher=

    2019

  33. [33]

    Random Struct Algor

    Szabó, Zoltán , title =. Random Struct Algor. , volume =

  34. [34]

    Geometric and Functional Analysis , volume =

    William Timothy Gowers , title =. Geometric and Functional Analysis , volume =

  35. [35]

    2024 , eprint=

    R(5,5) 46 , author=. 2024 , eprint=

    2024

  36. [36]

    Paul , title =

    Michal Kouril and Jerome L. Paul , title =. Experimental Mathematics , volume =

  37. [37]

    Nieuw Arch.Wiskunde , pages =

  38. [38]

    Golomb and A

    S.W. Golomb and A. W. Hales , title =. 2002 , booktitle =

    2002

  39. [39]

    Erdős, Paul , title =. Bull. Amer. Math. Soc. , number =

  40. [40]

    Lavrov, Mikhail , title =. SIAM J. Discrete Math. , volume =

  41. [41]

    Ars Combinatoria , volume =

    Neil Hindman and Eric Tressler , title =. Ars Combinatoria , volume =

  42. [42]

    Mathematics Magazine , volume =

    Oren Patashnik , title =. Mathematics Magazine , volume =

  43. [43]

    Tatham, G

    S. Tatham, G. Taylor. Reaching Row 5 in Solitaire Army

  44. [44]

    and Hirschberg, Daniel S

    Bell, George I. and Hirschberg, Daniel S. and Guerrero-García, Pablo. The minimum size required of a solitaire army. Integers. 2007

    2007

  45. [45]

    and Slater, P.J

    Phillips, J.B. and Slater, P.J. An introduction to graph competition independence and enclaveless parameters. Graph. Theory Notes N.Y. 2001

    2001

  46. [46]

    H. L. Bodlaender. On the complexity of some coloring games. Int. J. Found. Comput. Sci. 1991

    1991

  47. [47]

    Two-Person Cooperative Games , volume =

    John Nash , journal =. Two-Person Cooperative Games , volume =

  48. [48]

    1944 , publisher=

    Theory of Games and Economic Behavior , author=. 1944 , publisher=

    1944

  49. [49]

    1928 , author =

    Zur Theorie der Gesellschaftsspiele , journal =. 1928 , author =

    1928

  50. [50]

    1976 , author =

    The polynomial-time hierarchy , journal =. 1976 , author =

    1976

  51. [51]

    , title =

    Cook, Stephen A. , title =. 1971 , booktitle =

    1971

  52. [52]

    1973 , author =

    Universal Sequential Search Problems , journal =. 1973 , author =

    1973

  53. [53]

    1978 , booktitle =

    Biased Positional Games , series =. 1978 , booktitle =

    1978

  54. [54]

    2008 , publisher=

    Combinatorial Games Tic-Tac-Toe Theory , author=. 2008 , publisher=

    2008

  55. [55]

    2002 , author =

    Positional Games and the Second Moment Method , journal =. 2002 , author =

    2002

  56. [56]

    Acta Mathematica Academiae Scientiarum Hungaricae , volume=

    Remarks on positional games I , author=. Acta Mathematica Academiae Scientiarum Hungaricae , volume=

  57. [57]

    On positional games , author=. J. Comb. Theory Ser. A. , volume=

  58. [58]

    1981 , author =

    Van der waerden and ramsey type games , journal =. 1981 , author =

    1981

  59. [59]

    1973 , author =

    On a combinatorial game , journal =. 1973 , author =

    1973

  60. [60]

    A. W. Hales and R. I. Jewett , Title =. Trans. Am. Math. Soc. , Volume =

  61. [61]

    1974 , publisher=

    Surreal Numbers: How Two Ex-students Turned on to Pure Mathematics and Found Total Happiness: a Mathematical Novelette , author=. 1974 , publisher=

    1974

  62. [62]

    1982 , publisher=

    Winning Ways for Your Mathematical Plays , author=. 1982 , publisher=

    1982

  63. [63]

    Combinatorics Advances , pages=

    Unsolved problems in combinatorial games , author=. Combinatorics Advances , pages=. 1995 , publisher=

    1995

  64. [64]

    Conway, J. H. , address =. On numbers and games , year =. On numbers and games , isbn =

  65. [65]

    , Title =

    Sprague, R. , Title =. T\^ohoku Math J , Volume =. 1936 , Language =

    1936

  66. [66]

    Grundy, P. M. , Title =. Eureka (The Archimedeans' Journal) , Volume =

  67. [67]

    1901 , author =

    Nim, Game with Complete Mathematical Theory , journal =. 1901 , author =

    1901

  68. [68]

    Mathematical Games

    Martin Gardner. Mathematical Games. Scientific American. 1981

    1981

  69. [69]

    1865 , pages =

    Carrol, Lewis , title =. 1865 , pages =. doi:, zbl =

  70. [70]

    1886 , pages =

    Carrol, Lewis , title =. 1886 , pages =. doi:, zbl =

  71. [71]

    1914 , pages =

    Loyd, Sam , title =. 1914 , pages =. doi:, zbl =

    1914

  72. [72]

    and Ponciano, Vitor S

    Dourado, Mitre C. and Ponciano, Vitor S. and. On the monophonic rank of a graph , journal =. 2022 , mrnumber =

    2022

  73. [73]

    On the pathwidth of chordal graphs , author =. Discret. Appl. Math. , volume =. 1993 , publisher =

    1993

  74. [74]

    Ars Combinatoria , volume =

    Characterizing intersection graphs of substars of a star , author =. Ars Combinatoria , volume =. 2006 , mrnumber =

    2006

  75. [75]

    Journal of the ACM (JACM) , volume =

    On the hardness of approximating minimization problems , author =. Journal of the ACM (JACM) , volume =. 1994 , publisher =

    1994

  76. [76]

    Discrete & Computational Geometry , volume =

    On weak -nets and the Radon number , author =. Discrete & Computational Geometry , volume =. 2020 , publisher =

    2020

  77. [77]

    Near-linear-time algorithm for the geodetic Radon number of grids , author =. Discret. Appl. Math. , volume =. 2016 , publisher =

    2016

  78. [78]

    Discrete Mathematics , volume =

    On the geodetic Radon number of grids , author =. Discrete Mathematics , volume =. 2013 , publisher =

    2013

  79. [79]

    Graph minors. II. Algorithmic aspects of tree-width , author =. Journal of algorithms , volume =. 1986 , publisher =

    1986

  80. [80]

    Diskret analiz , volume =

    On an estimate of the chromatic class of a p-graph , author =. Diskret analiz , volume =. 1964 , mrnumber =

    1964

Showing first 80 references.