Goldberg's density conjecture

Let GG be a finite, undirected, loopless multigraph. Write Δ(G)\Delta(G) for its maximum degree, χ′(G)\chi'(G) for its chromatic index, and define its density by

Γ(G):=max⁡H⊆G, ∣H∣≥2⌈∣E(H)∣⌊∣H∣/2⌋⌉.\Gamma(G):=\max_{H\subseteq G,\ |H|\ge2}\left\lceil\frac{|E(H)|}{\lfloor |H|/2\rfloor}\right\rceil.

Goldberg's density conjecture. For any graph GG, if Γ(G)≤Δ(G)−1\Gamma(G)\le\Delta(G)-1, then

χ′(G)=Δ(G).\chi'(G)=\Delta(G).

The conjecture concerns when the maximum degree alone determines the chromatic index. The source notes that the Goldberg--Seymour conjecture has recently been confirmed, but does not state that this density conjecture itself has been resolved.

References

Primary source

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

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.