We 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 (P"1,P"2,...,P"n). The players take turns colouring G with colours from {1,...,n} such that for each i=1,2,...,n the induced subgraph G[V"i] (V"i is the set of vertices of G with colour i) has the property P"i after each move of the players. If after |V(G)| moves the graph G is (P"1,P"2,...,P"n)-partitioned (generalised coloured) then Alice wins. In this case, we say that the graph G has the property P"1@?...@?P"n. 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@?O"1)-game on acyclic graphs. Also some open problems are posed.
['Mieczysław Borowiecki', 'Elżbieta Sidorowicz']
Generalised game colouring of graphs