Geodesic
Nearly antipodal chromatic number $ac'(P_n)$ of the path $P_n$
Mathematica Bohemica, Tome 134 (2009) no. 1, pp. 77-86

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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.
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.
DOI : 10.21136/MB.2009.140642
Classification : 05C12, 05C15, 05C78
Keywords: radio $k$-coloring; span; radio $k$-chromatic number 
Kola, Srinivasa Rao; Panigrahi, Pratima. Nearly antipodal chromatic number $ac'(P_n)$ of the path $P_n$. Mathematica Bohemica, Tome 134 (2009) no. 1, pp. 77-86. doi: 10.21136/MB.2009.140642
@article{10_21136_MB_2009_140642,
     author = {Kola, Srinivasa Rao and Panigrahi, Pratima},
     title = {Nearly antipodal chromatic number $ac'(P_n)$ of the path $P_n$},
     journal = {Mathematica Bohemica},
     pages = {77--86},
     year = {2009},
     volume = {134},
     number = {1},
     doi = {10.21136/MB.2009.140642},
     mrnumber = {2504690},
     zbl = {1212.05236},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2009.140642/}
}
TY  - JOUR
AU  - Kola, Srinivasa Rao
AU  - Panigrahi, Pratima
TI  - Nearly antipodal chromatic number $ac'(P_n)$ of the path $P_n$
JO  - Mathematica Bohemica
PY  - 2009
SP  - 77
EP  - 86
VL  - 134
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2009.140642/
DO  - 10.21136/MB.2009.140642
LA  - en
ID  - 10_21136_MB_2009_140642
ER  - 
%0 Journal Article
%A Kola, Srinivasa Rao
%A Panigrahi, Pratima
%T Nearly antipodal chromatic number $ac'(P_n)$ of the path $P_n$
%J Mathematica Bohemica
%D 2009
%P 77-86
%V 134
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2009.140642/
%R 10.21136/MB.2009.140642
%G en
%F 10_21136_MB_2009_140642

[1] Chartrand, G., Erwin, D., Harary, F., Zhang, P.: Radio labelings of graphs. Bull. Inst. Combin. Appl. 33 (2001), 77-85. | MR | Zbl

[2] Chartrand, G., Erwin, D., Zhang, P.: Radio antipodal colorings of cycles. Congr. Numerantium 144 (2000), 129-141. | MR | Zbl

[3] Chartrand, G., Erwin, D., Zhang, P.: Radio antipodal colorings of graphs. Math. Bohem. 127 (2002), 57-69. | MR | Zbl

[4] Chartrand, G., Nebeský, L., Zhang, P.: Radio $k$-colorings of paths. Discuss. Math., Graph Theory 24 (2004), 5-21. | DOI | MR | Zbl

[5] Khennoufa, R., Togni, O.: A note on radio antipodal colourings of paths. Math. Bohem. 130 (2005), 277-282. | MR | Zbl

[6] Liu, D., Zhu, X.: Multi-level distance labelings for paths and cycles. SIAM J. Discrete Math. 19 (2005), 610-621. | DOI | MR

[7] Mustapha Kchikech, Riadh Khennoufa, Olivier Togni: Linear and cyclic radio $k$-labelings of trees. Discuss. Math., Graph Theory 27 (2007), 105-123. | DOI | MR

Cité par Sources :