Wheel graphs and their Game Chromatic Numbers

Question

How can I find the game chromatic numbers of wheel graphs?

I found the chromatic numbers. If the number of vertices is even, the chromatic number is 4, and if it is odd, the chromatic number is 3. However, I am not sure in which case what the game chromatic number is. Can you please help me?

Answer 1

The first player - who wants to successfully color the graph - can begin by coloring the center vertex. After this, every vertex colored will have at most three previously colored neighbors, so with four colors the first player can always win. Therefore the game chromatic number is at most $4$.

When the outer cycle is an odd cycle, the ordinary chromatic number is at least $4$, and therefore the game chromatic number can only be $4$.

When the outer cycle is even, we must check whether the game chromatic number can be $3$ - so we consider what happens when we play the coloring game with three colors. Here, it's important to realize that the $3$-coloring of the wheel graph is essentially unique (up to permuting the colors). So the second player can thwart the three coloring by doing anything that does not occur in this unique $3$-coloring. There are two cases:

Case 1. If the first player begins by playing on the outer cycle of the wheel graph, the second player can immediately win in two ways. The second player could take an odd number of steps around the outer cycle, and play the same color. Or, the second player could take an even number of steps around the outer cycle, and play a different color. Neither of these can occur in the unique $3$-coloring, so the first player is doomed.

Case 2. If the first player begins by playing on the center, the second player cannot immediately win: all possible moves can be described as "play on the outer cycle in a different color", and all of these are consistent with the unique $3$-coloring. The second player must hope that after the first player's second move, there will still be some counterplay left.

Let $x$ be the center vertex, let $y$ be the vertex of the second player's first move, and let $z$ be the vertex of the first player's second move. If there is a vertex not adjacent to $y$ or to $z$, then the second player can move there, and color that vertex inconsistently with the unique $3$-coloring - and win. Such a vertex is guaranteed to exist if the wheel graph has $9$ or more vertices. Therefore in all such cases, the game chromatic number is $4$.

Finally, in a wheel graph with $5$ or $7$ vertices, the first player can win the coloring game with $3$ colors, and the game chromatic number is $3$. The strategy is:

1. As the first move, play in the center.
2. As the second move, play opposite the second player's first move. (Use the color consistent with the unique $3$-coloring.)

Now the remaining vertices will have only one color available, which will lead to the graph being completely colored.