Average degrees of edge-chromatic critical graphs

Abstract Let G be a simple graph, and let Δ ( G ) , d ¯ ( G ) and χ ′ ( G ) denote the maximum degree, the average degree and the chromatic index of G , respectively. We called G edge- Δ -critical if χ ′ ( G ) = Δ ( G ) + 1 and χ ′ ( H ) ≤ Δ ( G ) for every proper subgraph H of G . Vizing in 1968 conjectured that if G is an edge- Δ -critical graph of order n , then d ¯ ( G ) ≥ Δ ( G ) − 1 + 3 n . We prove that for any edge- Δ -critical graph G , d ( G ) ≥ min 2 2 Δ ( G ) − 3 − 2 2 2 + 1 , 3 Δ ( G ) 4 − 2 , that is, d ¯ ( G ) ≥ 3 4 Δ ( G ) − 2 if Δ ( G ) ≤ 75 ; 2 2 Δ ( G ) − 3 − 2 2 2 + 1 ≈ 0 . 7388 Δ ( G ) − 1 . 153 if Δ ( G ) ≥ 76 . This result improves the best known bound 2 3 ( Δ ( G ) + 2 ) obtained by Woodall in 2007 for Δ ( G ) ≥ 41 .