Paper detail

Randomized $Δ$-Edge-Coloring via Quaternion of Complex Colors

This paper explores the application of a new algebraic method of color exchanges to the edge coloring of simple graphs. Vizing's theorem states that the edge coloring of a simple graph $G$ requires either $Δ$ or $Δ+1$ colors, where $Δ$ is the maximum vertex degree of $G$. Holyer proved that it is {\bf NP}-complete to decide whether $G$ is $Δ$-edge-colorable even for cubic graphs. By introducing the concept of complex colors, we show that the color-exchange operation follows the same multiplication rules as quaternion. An initially $Δ$-edge-colored graph $G$ allows variable-colored edges, which can be eliminated by color exchanges in a manner similar to variable eliminations in solving systems of linear equations. The problem is solved if all variables are eliminated and a properly $Δ$-edge-colored graph is reached. For a randomly generated graph $G$, we prove that our algorithm returns a proper $Δ$-edge-coloring with a probability of at least 1/2 in $O(Δ|V||E|^5)$ time if $G$ is $Δ$-edge-colorable. Otherwise, the algorithm halts in polynomial time and signals the impossibility of a solution, meaning that the chromatic index of $G$ probably equals $Δ+1$. Animations of the edge-coloring algorithms proposed in this paper are posted at YouTube http://www.youtube.com/watch?v=KMnj4UMYl7k.