On degree-colorings of multigraphs

Abstract

A notion of degree-coloring is introduced; it captures some, but not all properties of standard edge-coloring. We conjecture that the smallest number of colors needed for degree-coloring of a multigraph $G$ [the degree-coloring index $\tau (G)$] equals $\max \{\Delta ,\omega \}$, where $\Delta$ and $\omega$ are the maximum vertex degree in $G$ and the multigraph density, respectively. We prove that the conjecture holds iff $\tau (G)$ is a monotone function on the set of multigraphs.

5 pages; 2 figures