Bulletin of the
Korean Mathematical Society
BKMS

ISSN(Print) 1015-8634 ISSN(Online) 2234-3016

Article

HOME ALL ARTICLES View

Bull. Korean Math. Soc. 2018; 55(5): 1397-1404

Online first article June 29, 2018      Printed September 30, 2018

https://doi.org/10.4134/BKMS.b170813

Copyright © The Korean Mathematical Society.

The range of $r$-maximum index of graphs

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

Stats or Metrics

Share this article on :

Related articles in BKMS