A conditional greedy algorithm for edge-coloring

Mark K. Goldberg

We present a novel algorithm for edge-coloring of multigraphs. The correctness of this algorithm for multigraphs with ${\chi }^{\prime }>\Delta +1$ (${\chi }^{\prime }$ is the chromatic edge number and $\Delta$ is the m…