Definition of the game chromatic number and game colouring number of a graph

Suppose G  is a graph and C  is a set of colors. Alice and Bob play the following coloring game on G. Alice and Bob alternate their turns in coloring the vertices of G. At each turn, the player choose an uncolored vertex x  and color it with a color from C  which is not used by any of the colored neighbors of x. Alice has the first move. The game ends if no more moves are possible-- which happens if either all vertices are colored, or there are uncolored vertices, but for each of the uncolored vertices, its colored neighbors used all the colors.

Who wins the game ?

If at the end of the game, all the vertices are colored, then Alice wins the game. Otherwise Bob wins.

The game chromatic number of G, denoted by chi_g(G), is the least number of colors in the color set C  so that Alice has a winning strategy.

As an warm up with this parameter, we consider the complete bipartite graph K_{n, n}, say for n >= 4.

For two colors, Bob has a winning strategy: after Alice colors a vertex, Bob color another vertex of the same part with another color.

For three colors, Alice has a winning strategy: Suppose V(G)= X \cup Y. In the first step, Alice colors a vertex x in X. After Bob's move, Alice colors a vertex y in Y. As there are three colors, so there is always a legal color. Afterward, the color of x is legal for every vertex of X and the color of y is legal for every vertex of Y.

Let M be a perfect matching of K_{n, n}. We leave it to the readers to prove that chi_g(K_{n, n} \ M ) = n.

¡@

The game colouring number of G  is a variation of chi_g(G). Alice and Bob play an ordering game on G . Alice selects the first vertex, Bob selects the second vertex, Alice selects the third vertex, and so on. At the end, a linear ordering L  of the vertex set of G  is produced. The back degree of a vertex  x  is the number of neighbours of x  selected before x . The back degree of L is equal to the maximum of the back degree of all the vertices.  Alice's goal is to minimize the back degree of L , while Bob's goal to maximize the back degree of L .  The game colouring number  col_g(G)  of G is the least integer k  such that Alice has a strategy to ensure the produced linear ordering L  has back degree at most k-1.