Average degree conjecture for critical multigraphs

Let GG be a finite, undirected, loopless multigraph. Write Δ=Δ(G)\Delta=\Delta(G) for its maximum degree, χ(G)\chi'(G) for its chromatic index, and d(G)\overline{d}(G) for its average degree. The graph GG is Δ\Delta-critical when it is critical and χ(G)=Δ+1\chi'(G)=\Delta+1, where critical means that every proper subgraph HGH\subset G has χ(H)<χ(G)\chi'(H)<\chi'(G). The average degree conjecture. Every Δ\Delta-critical graph GG with Δ2\Delta\ge2 satisfies

d(G)2Δ+23.\overline{d}(G)\ge\frac{2\Delta+2}{3}.

The paper proves this bound for Δ{2,3,4,5,6,7,8}\Delta\in\{2,3,4,5,6,7,8\}, while the conjecture remains open in general; the proposed bound is stated to be best possible.

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

2 papers in this index state this conjecture (2016–2026). The statement above is taken from the most recent of them; the others are arXiv:1606.09101.

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.