A comparison of two edge-coloring formulations (Q688209)

Vizing's theorem asserts that the chromatic index \(\chi(G)\) is either \(\Delta(G)\) or \(\Delta(G)+1\), where \(\Delta(G)\) is the maximum degree of a graph \(G\). However, determining which of these two alternatives holds is NP-complete. This paper provides a polyhedral formulation for determining \(\chi(G)\), by which it is allowed analytically and computationally to compare to the set-partitioning formulation. Some valid inequalities for this formulation are established.