THE RANGE OF r-MAXIMUM INDEX OF GRAPHS

Abstract

For a connected graph G, an r-maximum edge-coloring is an edge-coloring f defined on E(G) such that at every vertex v with d(G) (v) >= r exactly r incident edges to v receive the maximum color. The r-maximum index x(r')(G) is the least number of required colors to have an r-maximum edge coloring of G. In this paper, we show how the rmaximum index is affected by adding an edge or a vertex. As a main result, we show that for each r >= 3 the r-maximum index function over the graphs admitting an r-maximum edge-coloring is unbounded and the range is the set of natural numbers. In other words, for each r > 3 and k >= 1 there is a family of graphs G (r , k) with x(r)' (G(r, k)) = k. Also, we construct a family of graphs not admitting an r-maximum edge-coloring with arbitrary maximum degrees: for any fixed r >= 3, there is an infinite family of graphs = {G(k) : k >= r +1}, where for each k >= r + 1 there is no r-maximum edge-coloring of G(k) and Delta(G(k)) = k.