Colouring games on outerplanar graphs and trees (Q1025941)

Let \(f\) be a function which assigns to each graph \(G\) a nonnegative integer \(f(G)\leq |V(G)|\). An \(f\) colouring of a graph \(G\) is mapping \(\varepsilon\) which assigns to each vertex of \(G\) a colour so that any subraph \(H\) of \(G\) receives at least \(f(H)\) colours. The \(f\)-chromatic number \(\chi(f, G)\) is the least number of colours used in an \(f\)-colouring of \(G\). This generalization of the chromatic number of graphs was introduced by Nešetřil and Ossona de Mendez. In the present paper the \(f\)-game chromatic number \(\chi_g(f, G)\) of a graph \(G\) is introduced in terms of a two person colouring game on graphs. \(\chi_g(f, G)\) is the least number of colours in the colour set \(X\) so that the first of the two players has a winning strategy. Moreover, the acyclic game chromatic number of a graph \(G\) is defined. It is proved that every outerplanar graph has an acyclic game chromatic number at least 7. Further results concern the game chromatic number of trees and forests.