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) \ge r$ exactly $r$ incident edges to $v$ receive the maximum color. The $r$-maximum index $\chi_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 $r$-maximum index is affected by adding an edge or a vertex. As a main result, we show that for each $r \ge 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 \ge 3$ and $k \ge 1$ there is a family of graphs $G(r, k)$ with $\chi_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 \ge 3$, there is an infinite family of graphs $\mathcal{F}_r = \{ G_k \colon k \ge r+1 \}$, where for each $k \ge r+1$ there is no $r$-maximum edge-coloring of $G_k$ and $\Delta(G_k) = k$.