On the size of edge-chromatic critical graphs
Let \(G\) be a graph with \(n\) vertices, \(m\) edges, edge-chromatic number \(\chi'(G)\) and maximum degree \(\Delta\). A conjecture of V. G. Vizing states that if \(\chi'(G)= \Delta+ 1\), but \(\chi'(G- e)< \chi'(G)\) for all edges \(e\) of \(G\), then \(m\geq {1\over 2}(n(\Delta- 1)+ 3)\). This inequality was proved for \(\Delta\leq 4\). In this paper the conjecture is proved for \(\Delta= 5\).
scientific article; zbMATH DE number 644731