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

About 21 years old · traced to

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+3∣G∣.\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.

References

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.