The relaxed game chromatic index of \(k\)-degenerate graphs (Q879391): Difference between revisions

The \((r,d)\)-relaxed edge-coloring game is a two-player game on the edge set of a graph \(G\) observing the rules that not more than \(r\) colors are used and that each edge is incident with at most \(d\) other edges of the same color. The \(d\)-relaxed game chromatic index \({^d\chi_g'}(G)\) of \(G\) is the least number \(r\) of colors such that there is a winning strategy for player \(A\), the first player. The author plays this game on trees and on \(k\)-degenerate graphs with maximum degree \(\Delta\). He gives winning strategies for player \(A\) in case of trees for \(r\geq\Delta+ 1\) and \(d\geq 1\) (i.e. he proves \({^d\chi_g'}(T)\leq\Delta+ 1\) for trees \(T\) when \(d\geq 1\)) and for \(r\geq\Delta\) and \(d\geq 3\), and in case of \(k\)-degenerate graphs for \(r\geq \Delta+ k- 1\) and \(d\geq 2k^2+ 4k\). This holds especially for outerplanar graphs with \(k= 2\) and for planar graphs with \(k= 5\).