Computer Science Department
School of Computer Science, Carnegie Mellon University


Edge Coloring, Polyhedra and Probability

Ljubomir Perkovic'

November 1998

Ph.D. Thesis

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

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.

160 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by