Vizing's average degree conjecture for edge-Δ-critical simple graphs

Let GG be a finite, undirected, loopless simple graph, let G|G| denote its number of vertices, let Δ=Δ(G)\Delta=\Delta(G) be its maximum degree, and let d(G)\overline{d}(G) be its average degree. The graph GG is Δ\Delta-critical if it is critical and has chromatic index χ(G)=Δ+1\chi'(G)=\Delta+1. Vizing's average degree conjecture. Every Δ\Delta-critical simple graph GG satisfies

d(G)Δ1+3G.\overline{d}(G) \ge \Delta-1+\frac{3}{|G|}.

The conjecture gives a lower bound on the density of edge-chromatic critical simple graphs. A number of results improve lower bounds, but the conjectured bound remains open.

Sources & referencesView supporting material

Primary source

Guantao Chen, Yuying Ma, Yimo Su and Shengze Wang, “Average degrees of edge-Δ-critical multigraphs”, arXiv:2606.12271 (2026).

Additional references

9 papers in this index state this conjecture (2005–2026). The statement above is taken from the most recent of them; the others are arXiv:2302.12914, arXiv:2301.02140, arXiv:1909.01260, arXiv:1904.12060, arXiv:1805.05996, arXiv:1506.02576, arXiv:1401.4568, arXiv:math/0512518.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.