Relaxed game chromatic number of graphs (Q1868839): Difference between revisions

This paper discusses the following coloring game on graphs: Let \(k,d\) be non-negative integers and \(C\) a set of \(k\) colors. Two persons, A and B, alternately color the vertices of \(G\) with colors from \(C\), with A having the first move. A color \(i\) is legal for an uncolored vertex \(x\) if by coloring \(x\) with color \(i\), the subgraph of \(G\) induced by those vertices of color \(i\) has maximum degree at most \(d\). Each move of A or B colors an uncolored vertex with a legal color. The game is over if either all vertices are colored, or no more vertices can be colored with a legal color. A's goal is to produce a legal coloring which colors all the vertices of \(G\), and B's goal is to prevent this from happening. It is proved that A has a winning strategy if \(G\) is a forest for \(k=3\) and \(d\geq 1\) or \(G\) is an outerplanar graph for \(k=6\) and \(d\geq 1\).