Randomized Δ-Edge-Coloring via Exchange of Complex Colors
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.
About the Speaker
Tony T. Lee received his BSEE degree from National Cheng Kung University, Taiwan in 1971, and his MS and PhD degrees in electrical engineering from Polytechnic University in New York, in 1976 and 1977, respectively. Currently, he is a Chair Professor at the Electronic Engineering Department of Shanghai Jiao Tong University. He was a Professor of Information Engineering at the Chinese University of Hong Kong from 1993 to 2010, and a Professor of Electrical Engineering at Polytechnic University of New York from 1991 to 1993. He was with AT&T Bell Laboratories, Holmdel, NJ, from 1977 to 1983, and Bellcore, currently Telcordia Technologies, Morristown, NJ, from 1983 to 1993. He is now serving as an Editor of the IEEE Transactions on Communications, and an area Editor of Journal of Communication Network. Tony is a fellow of IEEE and HKIE. He has received many awards including the 1989 Leonard G. Abraham Prize Paper Award from IEEE Communication Society, the 1999 Outstanding Paper Award from IEICE of Japan, and the 1999 National Natural Science Award from China.