Average degree conjecture for critical multigraphs

About 10 years old · traced to

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 H⊂GH\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.

References

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.