Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 31532
The Game of Col on Complete K-ary Trees

Authors: Alessandro Cincotti, Timothee Bossart


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

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 950


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