The 6-relaxed game chromatic number of outerplanar graphs

AbstractSuppose G is a graph and k,d are integers. The (k,d)-relaxed colouring game on G is a game played by two players, Alice and Bob, who take turns colouring the vertices of G with legal colours from a set X of k colours. Here a colour i is legal for an uncoloured vertex x if after colouring x with colour i, the subgraph induced by vertices of colour i has maximum degree at most d. Alice’s goal is to have all the vertices coloured, and Bob’s goal is the opposite: to have an uncoloured vertex without a legal colour. The d-relaxed game chromatic number of G, denoted by χg(d)(G), is the least number k so that when playing the (k,d)-relaxed colouring game on G, Alice has a winning strategy. This paper proves that if G is an outerplanar graph, then χg(d)(G)≤2 for d≥6