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 = (V, E), and is it denoted by chi(G). It is easy to see that if Delta is the maximum degree of G, then chi(G) >= Delta. Vizing has shown in 1965 the less obvious upper bound chi(G) <= Delta + 1. In fact, Vizing's constructive proof provides a O(n^4) algorithm for edge coloring G with Delta + 1 colors. Surprisigly, it is NP-complete to decide whether chi(G) = Delta or chi(G) = Delta + 1.
Hilton made a conjecture in 1985 that, if true, would imply that if Delta > |V|/3 then G can be optimally edge-colored in polynomial time. Note that almost all graphs satisfy the condition Delta > |V|/3.
In the seminar, I will present some of the progress I made (jointly with B. Reed) towards resolving Hilton's conjecture. I will show how our results are used to develop a deterministic algorithm for edge coloring whose running time is polynomial on average, assuming a uniform distribution of input graphs.
I will finally prove how the Hilton chain of hotels can improve its profits by coloring its bedsheets using 3 colors.