| Title:
|
Nearly antipodal chromatic number $ac'(P_n)$ of the path $P_n$ (English) |
| Author:
|
Kola, Srinivasa Rao |
| Author:
|
Panigrahi, Pratima |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
134 |
| Issue:
|
1 |
| Year:
|
2009 |
| Pages:
|
77-86 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
Chartrand et al.\ (2004) have given an upper bound for the nearly antipodal chromatic number $ac'(P_n)$ as $\binom {n-2}2+2$ for $n \geq 9$ and have found the exact value of $ac'(P_n)$ for $n=5,6,7,8$. Here we determine the exact values of $ac'(P_n)$ for $n \geq 8$. They are $2p^2-6p+8$ for $n=2p$ and $2p^2-4p+6$ for $n=2p+1$. The exact value of the radio antipodal number $ac(P_n)$ for the path $P_n$ of order $n$ has been determined by Khennoufa and Togni in 2005 as $2p^2-2p+3$ for $n=2p+1$ and $2p^2-4p+5$ for $n=2p$. Although the value of $ac(P_n)$ determined there is correct, we found a mistake in the proof of the lower bound when $n=2p$ (Theorem $6$). However, we give an easy observation which proves this lower bound. (English) |
| Keyword:
|
radio $k$-coloring |
| Keyword:
|
span |
| Keyword:
|
radio $k$-chromatic number |
| MSC:
|
05C12 |
| MSC:
|
05C15 |
| MSC:
|
05C78 |
| idZBL:
|
Zbl 1212.05236 |
| idMR:
|
MR2504690 |
| DOI:
|
10.21136/MB.2009.140642 |
| . |
| Date available:
|
2010-07-20T17:49:00Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140642 |
| . |
| Reference:
|
[1] Chartrand, G., Erwin, D., Harary, F., Zhang, P.: Radio labelings of graphs.Bull. Inst. Combin. Appl. 33 (2001), 77-85. Zbl 0989.05102, MR 1913399 |
| Reference:
|
[2] Chartrand, G., Erwin, D., Zhang, P.: Radio antipodal colorings of cycles.Congr. Numerantium 144 (2000), 129-141. Zbl 0976.05028, MR 1817928 |
| Reference:
|
[3] Chartrand, G., Erwin, D., Zhang, P.: Radio antipodal colorings of graphs.Math. Bohem. 127 (2002), 57-69. Zbl 0995.05056, MR 1895247 |
| Reference:
|
[4] Chartrand, G., Nebeský, L., Zhang, P.: Radio $k$-colorings of paths.Discuss. Math., Graph Theory 24 (2004), 5-21. Zbl 1056.05053, MR 2118291, 10.7151/dmgt.1209 |
| Reference:
|
[5] Khennoufa, R., Togni, O.: A note on radio antipodal colourings of paths.Math. Bohem. 130 (2005), 277-282. Zbl 1110.05033, MR 2164657 |
| Reference:
|
[6] Liu, D., Zhu, X.: Multi-level distance labelings for paths and cycles.SIAM J. Discrete Math. 19 (2005), 610-621. MR 2191283, 10.1137/S0895480102417768 |
| Reference:
|
[7] Mustapha Kchikech, Riadh Khennoufa, Olivier Togni: Linear and cyclic radio $k$-labelings of trees.Discuss. Math., Graph Theory 27 (2007), 105-123. MR 2321426, 10.7151/dmgt.1348 |
| . |
