Vizing's average degree conjecture for edge-Δ-critical simple graphs
Vizing's average degree conjecture for edge-Δ-critical simple graphs
Let be a finite, undirected, loopless simple graph, let denote its number of vertices, let be its maximum degree, and let be its average degree. The graph is -critical if it is critical and has chromatic index . Vizing's average degree conjecture. Every -critical simple graph satisfies
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.