Bounds on the Size of Critical Edge-Chromatic Graphs

By Vizing’s theorem, the chromatic index \(\chi'(G)\) of a simple graph \(G\) satisfies \(\Delta(G) \leq \chi'(G) \leq \Delta(G) + 1\); if \(\chi'(G) = \Delta(G)\), then \(G\) is class \(1\), otherwise \(G\) is class \(2\). A graph \(G\) is called critical edge-chromatic graph if \(G\) is connected, class \(2\) and \(\chi'(H) < \chi'(G)\) for all proper subgraphs \(H\) of \(G\). We give new lower bounds for the size of \(\Delta\)-critical edge-chromatic graphs, for \(\Delta \geq 9\).