The range of $r$-maximum index of graphs
Bull. Korean Math. Soc. 2018 Vol. 55, No. 5, 1397-1404
https://doi.org/10.4134/BKMS.b170813
Published online September 30, 2018
Jeong-Ok Choi
Gwangju Institute of Science and Technology
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$.
Keywords : $r$-maximum edge-coloring, $r$-maximum index of graphs
MSC numbers : 05C15
Full-Text :

   

Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd