Edge Coloring of Multigraphs With Very High Multiplicities

Abstract

ABSTRACT Vizing's generalized theorem states that any multigraph with maximum degree and maximum multiplicity has an edge coloring with at most colors. The runtime of Vizing's algorithm, which can find such a coloring, scales quadratically with . This is an important drawback for multigraphs arising from applications like photonic networks, where edge degrees and multiplicities can be very high. In this work, we propose a new edge coloring algorithm for multigraphs, which scales linearly with . To the best of our knowledge, no existing edge coloring algorithm, using so few colors, scales less than quadratically with . We describe one algorithm that finds a near‐optimal coloring and another algorithm that finds an optimal coloring with and worst‐case time complexity, respectively. We verify the working mechanisms as well as the performance of these algorithms, both for purely random test inputs and for synthetic test inputs whose structure is based on real applications.