| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4650318 | Discrete Mathematics | 2008 | 7 Pages |
Suppose GG is a graph and k,dk,d are integers. The (k,d)(k,d)-relaxed colouring game on GG is a game played by two players, Alice and Bob, who take turns colouring the vertices of GG with legal colours from a set XX of kk colours. Here a colour ii is legal for an uncoloured vertex xx if after colouring xx with colour ii, the subgraph induced by vertices of colour ii has maximum degree at most dd. 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 dd-relaxed game chromatic number of GG, denoted by χg(d)(G), is the least number kk so that when playing the (k,d)(k,d)-relaxed colouring game on GG, Alice has a winning strategy. This paper proves that if GG is an outerplanar graph, then χg(d)(G)≤2 for d≥6d≥6.
