Edge Coloring, Polyhedra and Probability
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 G and is denoted by x'(G). 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 let x*(G) be the optimum of the linear programming relaxation (called the fractional chromatic index). For any graph G one can compute x*(G) in polynomial time but deciding whether x'(G) = delta or x'(G) = delta + 1 is NP-Complete. So it would be of interest to determine for which simple graphs x'(G) = X*(G) as we can compute x'(G) 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 G 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1998
- Accession Number
- ADA360975
Entities
People
- Ljubomir Perkovic
Organizations
- Carnegie Mellon University