PreprintCC BY 4.0arXiv
Vizing's theorem for signed multigraphs
Abstract
We prove that every finite loopless signed multigraph Σ=(G,σ) satisfies χ'(Σ)≤Δ(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.
Related
- A hill-climbing version of Vizing's theorem
- Hadwiger's classification theorem on the sphere via signed orthoscheme decompositions
- Generalized Duke's theorem for signed Graphs
- Analytic description of the phase transition of inhomogeneous multigraphs
- Decomposing multigraphs into two Class I subgraphs with prescribed maximum degrees
BibTeX
@misc{lu2026vizings,
title = {{Vizing's theorem for signed multigraphs}},
author = {You Lu and Jingru Zhao and Li Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33108},
eprint = {2609.33108},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33108},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Vizing's theorem for signed multigraphs
AU - You Lu
AU - Jingru Zhao
AU - Li Zhang
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33108
UR - https://arxiv.org/abs/2609.33108
AB - We prove that every finite loopless signed multigraph Σ=(G,σ) satisfies χ'(Σ)≤Δ(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.
ER -