Maximum edge-colorings of graphs
Stanislav Jendrol′, Michaela Vrbjarová · Discussiones Mathematicae Graph Theory · 2015
An r-maximum k-edge-coloring of G is a k-edge-coloring of G having a property that for every vertex v of degree d G (v) = d, d r, the maximum color, that is present at vertex v, occurs at v exactly r times. The r-maximum index r (G) is defined to be the minimum number k of colors needed for an r-maximum k-edge-coloring of graph G. In this paper we show that r (G) 3 for any nontrivial connected graph G and r = 1 or 2. The bound 3 is tight. All graphs G with 1 (G) = i, i = 1, 2, 3 are characterized. The precise value of the r-maximum index, r 1, is determined for trees and complete graphs.