Generalised game colouring of graphs (Q878606): Difference between revisions

There are two players, Alice and Bob, and they colour alternatively the vertices of a graph \(G\), with Alice having the first move. For a given set of hereditary properties \(\mathcal P_1,\mathcal P_2,\dots,\mathcal P_k\), the players take turns colouring \(G\) with colours from \(\{1,2,\dots,k\}\), such that for each \(i=1,2,\dots,k\) the subgraph induced by colour \(i\) has property \(\mathcal P_i\) after each move. If after \(| V(G)| \) moves the graph \(G\) is \((\mathcal P_1,\mathcal P_2,\dots,\mathcal P_k)\)-partitioned then Alice wins. In this case the graph \(G\) has property \(\mathcal P_1\square\mathcal P_2\square\cdots\square\mathcal P_k\). In the paper the class \(\mathcal O\square\mathcal O\) of graphs is characterized, where \(\mathcal O\) is the property that a graph is totally disconnected. A strategy for Alice for playing \((\mathcal O\square\mathcal O\square\mathcal O_1)\)-game on acyclic graphs (where \(\mathcal O_1\) is the property that the graph consists of isolated edges and vertices) is described.