Bounds for the chromatic index of signed multigraphs

Abstract

The paper studies edge-coloring of signed multigraphs and extends classical Theorems of Shannon and König to signed multigraphs. We prove that the chromatic index of a signed multigraph $(G,{\sigma }_G)$ is at most $\lfloor \frac{3}{2}\Delta (G)\rfloor$. Furthermore, the chromatic index of a balanced signed multigraph $(H,{\sigma }_H)$ is at most $\Delta (H)+1$ and the balanced signed multigraphs with chromatic index $\Delta (H)$ are characterized.

8 pages

References in corpus (1)

• Concepts of signed graph coloring