A comparison of two edge-coloring formulations

A fundamental theorem of Vizing relates the maximum degree, ℝ(G), of a simple graph G to the minimum number, &chi(G), of colors needed to color its edges. Vizing’s theorem asserts that &chi(G) is either ℝ(G) or ℝ(G)+1; however, determining which of these two alternatives holds is NP-complete. The authors present a polyhedral formulation for determining &chi(G), which they analytically and computationally compare to an earlier set-partitioning formulation. The authors also establish some valid inequalities for the present formulation.