Ljubomir Perković

Edge Coloring, Polyhedra and Probability Degree Type: Ph.D. in Algorithms, Combinatorics and Optimization
Advisor(s): Dana Scott, Bruce Reed
Graduated: December 1998

Abstract:

Edge Coloring is the following optimization problem:

Given a graph, how many colors are required to color its edges in such a way that no two edges which share an endpoint receive the same color?

The required number of colors is called the chromatic index of the graph. We consider the edge coloring problem in the framework of the relationship between an integer program and its linear programming relaxation. To do this we first formulate edge coloring as an integer program and we define the fractional chromatic index to be the optimum of its linear programming relaxation. For any graph of maximum degree D, one can compute the fractional chromatic index in polynomial time but deciding whether the chromatic index is D or D+1 is NP-Complete. So it would be of interest to determine for which classes of simple graphs is the chromatic index equal to the ceiling of the fractional chromatic index as we can compute the chromatic index for graphs in these classes.

In this thesis we show that large classes of graphs satisfy this equality. More precisely, we show that if a graph is large enough, has large maximum degree and satisfies two technical conditions, then the equality holds. The constructive proof provides a randomized polynomial time algorithm for optimally coloring the edges of such graphs. We use a deterministic version of this algorithm to design the first algorithm that computes an optimal edge coloring of any graph in polynomial time, on average.

Thesis Committee:
Bruce Reed (Co-Chair)
Dana Scott (Co-Chair)
Alan Frieze
Avrim Blum
Jeong Han Kim

James Morris, Head, Computer Science Department
Raj Reddy Dean, School of Computer Science

Keywords:
Graph theory, edge coloring, design and analysis of algorithms, combinatorial optimization, polyhedral combinatorics, probabilistic analysis of algorithms, randomized algorithms