Generalised game colouring of graphs

AbstractWe consider the version of a colouring game introduced by Bodlaender [On the complexity of some colorings games, Internat. J. Found. Comput. Sci. 2 (1991) 133–147]. We combine the concepts: this game and the generalised colouring of graphs as follows. The two players are Alice and Bob and they play alternatively with Alice having the first move. Let be given a graph G and an ordered set of hereditary properties (P1,P2,…,Pn). The players take turns colouring G with colours from {1,…,n} such that for each i=1,2,…,n the induced subgraph G[Vi] (Vi is the set of vertices of G with colour i) has the property Pi after each move of the players. If after |V(G)| moves the graph G is (P1,P2,…,Pn)-partitioned (generalised coloured) then Alice wins. In this case, we say that the graph G has the property P1□⋯□Pn. We characterise the class O□O of graphs and we give an answer to a question, for k=2, posed by Zhu [The game coloring number of planar graphs, J. Combin. Theory B 75 (1999) 245–258]. We describe a new strategy for Alice for playing the (O□O□O1)-game on acyclic graphs. Also some open problems are posed