Adapted game colouring of graphs

Suppose G = ( V , E ) is a graph and F is a colouring of its edges (not necessarily proper) that uses the colour set X . In an adapted colouring game, Alice and Bob alternately colour uncoloured vertices of G with colours from X . A partial colouring c of the vertices of G is legal if there is no edge e = x y such that c ( x ) = c ( y ) = F ( e ) . In the process of the game, each partial colouring must be legal. If eventually all the vertices of G are coloured, then Alice wins the game. Otherwise, Bob wins the game. The adapted game chromatic number of a graph G , denoted by χ adg ( G ) , is the minimum number of colours needed to ensure that for any edge colouring F of G , Alice has a winning strategy for the game. This paper studies the adapted game chromatic number of various classes of graphs. We prove that the maximum adapted game chromatic number of trees is 3 , the maximum adapted game chromatic number of outerplanar graphs is 5 , the adapted game chromatic number of partial k -trees is at most 2 k + 1 , and the adapted game chromatic number of planar graphs is at most 11 .