Radio k-colorings of paths

Gary Chartrand, Ladislav Nebeský, and Ping Zhang. "Radio k-colorings of paths." Discussiones Mathematicae Graph Theory 24.1 (2004): 5-21. <http://eudml.org/doc/270733>.

@article{GaryChartrand2004,
abstract = {For a connected graph G of diameter d and an integer k with 1 ≤ k ≤ d, a radio k-coloring of G is an assignment c of colors (positive integers) to the vertices of G such that d(u,v) + |c(u)- c(v)| ≥ 1 + k for every two distinct vertices u and v of G, where d(u,v) is the distance between u and v. The value rcₖ(c) of a radio k-coloring c of G is the maximum color assigned to a vertex of G. The radio k-chromatic number rcₖ(G) of G is the minimum value of rcₖ(c) taken over all radio k-colorings c of G. In this paper, radio k-colorings of paths are studied. For the path Pₙ of order n ≥ 9 and n odd, a new improved bound for $rc_\{n- 2\}(Pₙ)$ is presented. For n ≥ 4, it is shown that $rc_\{n-3\}(Pₙ) ≤ \binom\{n-2\}\{2\}$ Upper and lower bounds are also presented for rcₖ(Pₙ) in terms of k when 1 ≤ k ≤ n- 1. The upper bound is shown to be sharp when 1 ≤ k ≤ 4 and n is sufficiently large.},
author = {Gary Chartrand, Ladislav Nebeský, Ping Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {radio k-coloring; radio k-chromatic number; radio -coloring; -chromatic number; path},
language = {eng},
number = {1},
pages = {5-21},
title = {Radio k-colorings of paths},
url = {http://eudml.org/doc/270733},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Gary Chartrand
AU - Ladislav Nebeský
AU - Ping Zhang
TI - Radio k-colorings of paths
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 1
SP - 5
EP - 21
AB - For a connected graph G of diameter d and an integer k with 1 ≤ k ≤ d, a radio k-coloring of G is an assignment c of colors (positive integers) to the vertices of G such that d(u,v) + |c(u)- c(v)| ≥ 1 + k for every two distinct vertices u and v of G, where d(u,v) is the distance between u and v. The value rcₖ(c) of a radio k-coloring c of G is the maximum color assigned to a vertex of G. The radio k-chromatic number rcₖ(G) of G is the minimum value of rcₖ(c) taken over all radio k-colorings c of G. In this paper, radio k-colorings of paths are studied. For the path Pₙ of order n ≥ 9 and n odd, a new improved bound for $rc_{n- 2}(Pₙ)$ is presented. For n ≥ 4, it is shown that $rc_{n-3}(Pₙ) ≤ \binom{n-2}{2}$ Upper and lower bounds are also presented for rcₖ(Pₙ) in terms of k when 1 ≤ k ≤ n- 1. The upper bound is shown to be sharp when 1 ≤ k ≤ 4 and n is sufficiently large.
LA - eng
KW - radio k-coloring; radio k-chromatic number; radio -coloring; -chromatic number; path
UR - http://eudml.org/doc/270733
ER -