2016/12/25 by Goldberg, Mark K.
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1612.08306
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 τ(G)] equals max\Δ, ω\, where Δ and ω are the maximum vertex degree in G and the multigraph density, respectively. We prove that the conjecture holds iff τ(G) is a monotone function on the set of multigraphs.