Article

On game chromatic number analogues of Mycielsians and Brooks' Theorem

---

Abstract

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

Keywords: game chromatic number, Mycielskian, Brooks' Theorem

How to Cite:

Chamberlin, C., DeCapua, J., Elser, H., Gerraputa, D. & Hamm, A., (2019) “On game chromatic number analogues of Mycielsians and Brooks' Theorem”, North Carolina Journal of Mathematics and Statistics 5(1).