On the size of edge-coloring critical graphs with maximum degree 4

In 1968, Vizing proposed the following conjecture: If G=(V,E)G=(V,E) is a ΔΔ-critical graph of order nn and size mm, then m≥12[(Δ−1)n+3]. This conjecture has been verified for the cases of Δ≤5Δ≤5. In this paper, we prove that m≥74n when Δ=4Δ=4. It improves the known bound for Δ=4Δ=4 when n>6n>6.