The Game of Col on Complete K-ary Trees

Authors: Alessandro Cincotti, Timothee Bossart

Abstract:

Col is a classic combinatorial game played on graphs and to solve a general instance is a PSPACE-complete problem. However, winning strategies can be found for some specific graph instances. In this paper, the solution of Col on complete k-ary trees is presented.

Keywords: Combinatorial game, Complete k-ary tree, Mapcoloring game.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1057889

References:

[1] E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways For Your Mathematical Plays, 2nd ed. Natick, Massachusetts: A K Peters, 2001, vol. 1, ch. 2, pp. 37-39.
[2] J. H. Conway, On Numbers and Games, 2nd ed. Natick, Massachusetts: A K Peters, 2001, ch. 8, pp. 91-95.
[3] T. J. Schaefer, "On the complexity of some two-person perfect information games," J. Comput. Systems Sci., vol. 16, pp. 185-225, 1978.