Events

Randomized Δ-Edge-Coloring via Exchange of Complex Colors

Lecture / Panel

For NYU Community

Speaker: Professor Tony T. Lee

Host Faculty: Professor Jonathan Chao

Abstract

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 NP-complete to decide whether G is Δ-edge-colorable even for cubic graphs. By introducing the concept complex colored edges, we show that the color-exchange operation of complex colors 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. The Δ-edge-coloring problem of bipartite graphs is completely solved. The best known algorithm for finding a proper Δ-edge-coloring of a bipartite graph runs in time O(|E|logΔ) . The running time of our algorithm for bipartite graphs is on the order of O(|E|log|V|). As for non-bipartite graphs, the only known result is 3-edge-coloring of cubic planar graphs. As Tait proved that the 3-edge-coloring problem of bridgeless cubic planar graphs is equivalent to the four color map problem, the newly improved proof of four-color theorem actually can give rise to a quadratic algorithm for finding proper 3-edge-coloring of cubic planar graphs. Thus, our approach is the first randomized algorithm for finding Δ-edge-coloring of general graphs.