Relaxed Game Chromatic Number of Outer Planar Graphs

Abstract

In a \((k, d)\)-relaxed coloring game, two players, Alice and Bob, take turns coloring the vertices of a graph \(G\) with colors from a set \(C\) of \(k\) colors. A color \(c\) is legal for an uncolored vertex (at a certain step) means that after coloring \(x\) with color \(i\), the subgraph induced by vertices of color \(i\) has maximum degree at most \(d\). Each player can only color a vertex with a legal color. Alice’s goal is to have all the vertices colored, and Bob’s goal is the opposite: to have an uncolored vertex without legal color. The \(d\)-relaxed game chromatic number of a graph \(G\), denoted by \(\chi^{(d)}_g(G)\) is the least number \(k\) so that when playing the \((k,d)\)-relaxed coloring game on \(G\), Alice has a winning strategy. This paper proves that if \(G\) is an outer planar graph, then \(\chi^{(d)}_g(G) \leq 7 – d\) for \(d = 0, 1, 2, 3, 4\).