×
Zhao, Xiao; Chen, Sheng

Proper 2-coloring game on some trees. (English) Zbl 1425.05098

Theor. Comput. Sci. 778, 1-18 (2019).
Summary: Let \(\mathscr{P}^n\) denote the path with exactly \(n\) vertices and let \(\mathscr{T}^{n, i}\) denote the tree obtained from \(\mathscr{P}^{n - 1}\) by adding a to the \((i + 1)\)-th vertex of \(\mathscr{P}^{n - 1}\), where \(n \geq 4\) and \(1 \leq i \leq n - 3\). In this paper we study proper 2-coloring game on \(\mathscr{T}^{n, i}\) by using Sprague-Grundy function and give the optimal strategy of proper 2-coloring game on \(\mathscr{T}^{n, i}\).
© Elsevier B.V.

MSC:

05C57 Games on graphs (graph-theoretic aspects)
05C15 Coloring of graphs and hypergraphs
91A43 Games involving graphs
91A05 2-person games

Keywords:

proper 2-coloring game; tree; Sprague-Grundy function; optimal strategy
Cite Review PDF
Full Text: DOI

References:

[1] Beaulieu, G.; Burke, K.; Duchêne, E., Impartial coloring games, Theoret. Comput. Sci., 485, 49-60, 2013 · Zbl 1297.05160
[2] Beck, J., Combinatorial Games: Tic-Tac-Toe Theory, 2008, Cambridge University Press · Zbl 1196.91002
[3] Berlekamp, E. R.; Conway, J. H.; Guy, R. K., Winning Ways for Your Mathematical Plays, 1982, Academic Press · Zbl 0485.00025
[4] Byrnes, S., Poset game periodicity, Integers, 3, 2003, #G03 · Zbl 1128.91310
[5] Conway, J. H., On Numbers and Games, 1976, Academic Press: Academic Press London · Zbl 0334.00004
[6] Duchêne, E.; Fraenkel, A. S.; Nowakowski, R. J.; Rigo, M., Extensions and restrictions of Wythoff’s game preserving its P-positions, J. Combin. Theory Ser. A, 117, 545-567, 2010 · Zbl 1185.91061
[7] Fenner, S. A.; Rogersy, John, Combinatorial game complexity: an introduction with poset games, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 116, 42-75, 2015 · Zbl 1409.68137
[8] Fraenkel, A. S., New games related to old and new sequences, Appl. Math., 4, 1-18, 2004 · Zbl 1089.11017
[9] Grundy, P. M., Mathematics and games, Eureka, 2, 6-8, 1939
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.