GAME PARTITIONS OF GRAPHS

We denote by I the class of all finite simple graphs. A graph property is a nonempty isomorphism-closed subclass of I. A property P is called (induced) hereditary if it is closed under (induced) subgraphs. Given hereditary properties P1,P2,...,Pn, a vertex (P1,P2,...,Pn)-partition (generalized colouring) of a graph G ∈ I is a partition (V1, V2,..., V2) of V (G) such that for i = 1, 2,..., n the induced subgraph G[Vi] has the property Pi. We consider the version of colouring game. We combine: a colouring game and generalized colouring of graphs as follows. The two players are Alice and Bob and they play alternatively with Alice having the first move. Given a graph G and an ordered set of hereditary properties (P1,P2,...,Pn). The players take turns colouring of G with colours from {1, 2,..., 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 property Pi after each move of players. If after |V (G) | moves the graph G is (P1,P2,...,Pn)-partitioned (generalized coloured) then Alice wins. Above defined game we will call (P1,P2,...,Pn)-game. Some results and open problems on the (P1,P2,...,Pn)-game will be pre-sented