Vizing's theorem for signed multigraphs
We prove that every finite loopless signed multigraph $Σ=(G,σ)$ satisfies $χ'(Σ)\leqΔ(G)+μ(G)$, where $χ'(Σ)$ is its chromatic index, and $Δ(G)$ and $μ(G)$ are the maximum degree and maximum multiplicity of $G$, respectively. This bound is sharp, even when both positive and negative edges are present, and generalizes both Vizing's theorem for ordinary multigraphs and Behr's theorem for signed simple graphs.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.33108
curl -X POST /api/v1/records/arxiv/2609.33108/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.33108/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'