AN EDGE COLORING HEURISTIC BASED ON VIZING'S THEOREM
Tiago de Oliveira Januario · 2012
Vizing's theorem establishes that the edges of a simple graph can be properly colored using at most D+ 1 colors. Therefore, the minimum number of colors that are needed to color the edges of a graph G satisfies D c 0 (G) D+ 1 and a polynomial algorithm to obtain a D+ 1 coloring of the graph is known. Heuristics for the edge coloring problem do exist in the literature and can be justified in situations where a D+ 1 coloring of the graph is not good enough. In this paper, a constructive heuristic based on the proof of Vizing's theorem is proposed. The heuristic tries to find a D coloring of the graph, but whenever that coloring is not found, a solution using exactly D+ 1 colors is returned. Therefore, the heuristic obtains solutions whose cost is, in the worst case, one color above