{"id":"arxiv/2606.12271","url":"https://arxiv.org/abs/2606.12271","tags":["math.CO"],"score":0,"title":"Average degrees of edge-$Δ$-critical multigraphs","domain":"math.CO","source":"arxiv","authors":["Guantao Chen","Yuying Ma","Yimo Su","Shengze Wang"],"reviews":0,"subject":"math.CO","summary":"Let $G$ be a loopless multigraph with maximum degree $Δ(G)$, average degree $\\overline{d}(G)$, density $Γ(G)$, and chromatic index $χ'(G)$. A multigraph $G$ is called edge-$Δ$-critical if $Δ(G)=Δ$, $χ'(G)=Δ(G)+1$ and $χ'(H) \\le Δ(G)$ for every proper subgraph $H\\subset G$. Vizing conjectured that if $G$ is an edge-$Δ$-critical simple graph on $n$ vertices, then $\\overline{d}(G) \\ge Δ-1+\\tfrac{3}{n}$. Motivated by this, we conjecture that every edge-$Δ$-critical multigraph $G$ satisfies $\\overline{d}(G) \\ge \\tfrac{2Δ+2}{3}$, which is best possible. We first give a general lower bound in this…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-10","reactions":{}}