Game chromatic number of some network graphs (Q2195643)

Suppose that $G$ is a graph and $C$ is a set of colours. Alice and Bob play the following colouring game on $G$. Alice and Bob alternate their turns in colouring the vertices of $G$. At each turn, the player choose an uncoloured vertex $x$ and colour it with a colour from $C$ which is not used by any of the coloured neighbours of $x$. Alice has the first move. The game ends if no more moves are possible -- which happens if either all vertices are coloured, or there are uncoloured vertices, but for each of the uncoloured vertices, its coloured neighbours used all the colours. If at the end of the game, all the vertices are coloured, then Alice wins the game. Otherwise Bob wins. The game chromatic number of $G$, denoted by $\chi_g(G)$, is the least number of colours in the colour set $C$ so that Alice has a winning strategy. The authors of this paper determine the precise values of the $\chi_g$ of some interconnection network graph families such as: shuffle exchange network, cube-connected cycles and wrapped around butterflies. The entire exposition of the method of proof on each of the three instances is simple, neat and understandable.