The game chromatic number of generalized Mycielski graphs of paths and cycles

Yushuang Mou; Qiang Sun; Chao Zhang

paper

The game chromatic number of generalized Mycielski graphs of paths and cycles

arXiv:2609.02283

Abstract

The graph coloring game is a two-player game in which the players alternately color an uncolored vertex of a graph $G$ . The game chromatic number is the minimum number of colors needed for the first player to guarantee a win. We investigate this parameter for generalized Mycielski graphs $M_{k} (G)$ , where $G$ is a path $P_{n}$ or a cycle $C_{n}$ with $n$ vertices. For every $k \geq 2$ and $n \geq 5$ , we establish $4 \leq χ_{g} (M_{k} (P_{n})) \leq 5$ and $4 \leq χ_{g} (M_{k} (C_{n})) \leq 5$ . We also determine the exact values $χ_{g} (M_{2} (P_{5})) = χ_{g} (M_{2} (P_{6})) = 4$ . The proofs of the lower bounds use a configuration in which Bob can create two threats simultaneously, while the four-color upper bounds in the two exact cases are proved using the double-doctor lemma. Thus the number of layers and the order of the base graph may grow, but the game chromatic number remains bounded by five.

16 pages, 3 figures, 12 tables