Game Chromatic Index of Graphs with Given Restrictions on Degrees

Published in Theoretical Computer Science, 2008

A. Beveridge, T. Bohman, A. Frieze and O. Pikhurko, Game Chromatic Index of Graphs with Given Restrictions on Degrees, Theoretical Computer Science, 407 (2008), 242–249.

Preprint link: https://github.com/mathbeveridge/mathbeveridge.github.io/blob/master/files/GameChIndex.pdf

Given a graph $G$ and an integer $k$, two players alternatively color the edges of $G$ using $k$ colors so that adjacent edges get different colors. The game chromatic index $\chi_g’(G)$ is the minimum $k$ for which the first player has a strategy that ensures that all edges of $G$ get colored. The trivial bounds on the game chromatic index are $\Delta(G) \leq \chi’_g(G) \leq 2 \Delta(G) -1$ where $\Delta(G)$ is the maximal degree of $G$. We explore families of graphs at the two extremes.