Vizing's theorem for signed multigraphs

Abstract

We prove that every finite loopless signed multigraph $\Sigma =(G,\sigma )$ satisfies ${\chi }^{\prime }(\Sigma )\le \Delta (G)+\mu (G)$, where ${\chi }^{\prime }(\Sigma )$ is its chromatic index, and $\Delta (G)$ and $\mu (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.