The chromatic index of graphs with a spanning star

Abstract

Vizing’s Theorem states that any graph G has chromatic index either the maximum degree Δ(G) or Δ(G) + 1. If G has 2s + 1 points and Δ(G) = 2s, a well‐known necessary condition for the chromatic index to equal 2s is that G have at most 2s2 lines. Hilton conjectured that this condition is also sufficient. We present a proof of that conjecture and a corollary that helps determine the chromatic index of some graphs with 2s points and maximum degree 2s − 2.