# Radio k-colorings of paths

Gary Chartrand; Ladislav Nebeský; Ping Zhang

Discussiones Mathematicae Graph Theory (2004)

- Volume: 24, Issue: 1, page 5-21
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topGary 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 -

## References

top- [1] G. Chartrand, D. Erwin, F. Harary and P. Zhang, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33 (2001) 77-85. Zbl0989.05102
- [2] G. Chartrand, D. Erwin and P. Zhang, A graph labeling problem suggested by FM channel restrictions, Bull. Inst. Combin. Appl. (accepted). Zbl1066.05125
- [3] G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of cycles, Congr. Numer. 144 (2000) 129-141. Zbl0976.05028
- [4] G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of graphs, Math. Bohem. 127 (2002) 57-69. Zbl0995.05056
- [5] D. Fotakis, G. Pantziou, G. Pentaris and P. Sprirakis, Frequency assignment in mobile and radio networks, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 45 (1999) 73-90. Zbl0929.68005
- [6] W. Hale, Frequency assignment: theory and applications, Proc. IEEE 68 (1980) 1497-1980, doi: 10.1109/PROC.1980.11899.
- [7] J. van den Heuvel, R.A. Leese and M.A. Shepherd, Graph labeling and radio channel assignment, J. Graph Theory 29 (1998) 263-283, doi: 10.1002/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V Zbl0930.05087
- [8] Minimum distance separation between stations, Code of Federal Regulations, Title 47, sec. 73.207.

## Citations in EuDML Documents

top- Riadh Khennoufa, Olivier Togni, A note on radio antipodal colourings of paths
- Yu-Fa Shen, Guo-Ping Zheng, Wen-Jie HeK, Improved upper bounds for nearly antipodal chromatic number of paths
- Mustapha Kchikech, Riadh Khennoufa, Olivier Togni, Radio k-labelings for Cartesian products of graphs
- Srinivasa Rao Kola, Pratima Panigrahi, Nearly antipodal chromatic number $a{c}^{\text{'}}\left({P}_{n}\right)$ of the path ${P}_{n}$
- Mustapha Kchikech, Riadh Khennoufa, Olivier Togni, Linear and cyclic radio k-labelings of trees
- Futaba Fujie-Okamoto, Willem Renzema, Ping Zhang, The $k$-metric colorings of a graph

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.