The North Carolina Journal of Mathematics and Statistics

On game chromatic number analogues of Mycielsians and Brooks' Theorem

Chris Chamberlin, Jacob DeCapua, Hannah Elser, Dana Gerraputa, Arran Hamm


The vertex coloring game is a two-player game on a graph with given color set in which the first player attempts to properly color the graph and the second attempts to prevent a proper coloring from being achieved. The smallest number of colors for which the first player can win no matter how the second player plays is called the game chromatic number of the graph. In this paper we initiate the study of game chromatic number for Mycielskians and a game chromatic number analogue of Brooks' Theorem (which characterizes graphs for which chromatic number is at most the maximum degree of the graph). In particular, we determine the game chromatic number of Mycielskians of complete graphs, complete bipartite graphs, and cycles. In the direction of Brooks' Theorem, we show that if there are few vertices of maximum degree or if all vertices of maximum degree are at least three edges apart, then the game chromatic number is at most the maximum degree of the graph


game chromatic number; Mycielskian; Brooks' Theorem

Full Text:



Bartnicki, T., Bresar, B., Grytczuk, J., Kovse, M., Miechowicz, Z., and Peterin, I. (2008). Game chromatic number of cartesian product graphs. Elec. J. Comb., 15:R72.

Bartnicki, T., Grytczuk, J., Kierstead, H., and Zhu, X. (2007). The map-coloring game. Am. Math. Monthly, 114:793–803.

Destacamento, C., Rodriguez, A., and Aquino-Ruivivar, L. (2014). The game chromatic number of some classes of graphs.


Dinski, T. and Zhu, X. (1999). A bound for the game chromatic number of graphs. Disc. Math., 196(1-3):109–115.

Dunn, C., Larsen, V., Lindke, K., Retter, T., and Toci, D. (2015). The game chromatic number of trees and forests. Discrete Math. and Th. Comp. Sc., 17(2):31–48.

Faigle, U., Kern, U., Kierstead, H. A., and Trotter, W. T. (1993). On the game chromatic number of some classes of graphs. Ars Combin., 35:143–150.

Frieze, A., Haber, S., and Lavrov, M. (2013). On the game chromatic number of sparse random graphs. SIAM J. Discrete Math., 27(2):768–790.

Gardner, M. (1981). Mathematical games. Scientific American, 23.

Guan, D. and Zhu, X. (1999). Game chromatic number of outerplanar graphs. J. Graph Th., 30(1):67–70.

Kierstead, H. A. and Trotter, W. T. (1994). Planar graph coloring with an uncooperative partner. J. of Graph Th. , 18(6):564–584.

Raspaud, A. and Wu, J. (2009). Game chromatic number of toroidal grids. Info. Processing Letters, 109(21-22):1183–1186.

Zhu, X. (1999). The game coloring number of planar graphs.

J. Combin. Theory Ser. B, 75:245–258.