A conditional greedy algorithm for edge-coloring

Abstract

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 maximum vertex degree) would prove a long standing conjecture in edge-coloring of multigraphs.

4 pages