Average degrees of edge-$Δ$-critical multigraphs

Guantao Chen, Yuying Ma, Yimo Su, Shengze Wang

arXivarxiv/2606.12271Jun 10, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2606.12271
curl -X POST /api/v1/records/arxiv/2606.12271/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.12271/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'