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