Improved upper bounds for nearly antipodal chromatic number of paths
Yu-Fa Shen ; Guo-Ping Zheng ; Wen-Jie HeK
Discussiones Mathematicae Graph Theory, Tome 27 (2007), p. 159-174 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

For paths Pₙ, G. Chartrand, L. Nebeský and P. Zhang showed that ac'(Pₙ)≤n-22+2 for every positive integer n, where ac’(Pₙ) denotes the nearly antipodal chromatic number of Pₙ. In this paper we show that ac'(Pₙ)≤n-22-n/2-⎣10/n⎦+7 if n is even positive integer and n ≥ 10, and ac'(Pₙ)≤n-22-(n-1)/2-⎣13/n⎦+8 if n is odd positive integer and n ≥ 13. For all even positive integers n ≥ 10 and all odd positive integers n ≥ 13, these results improve the upper bounds for nearly antipodal chromatic number of Pₙ.

Publié le : 2007-01-01
EUDML-ID : urn:eudml:doc:270297 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1352,
     author = {Yu-Fa Shen and Guo-Ping Zheng and Wen-Jie HeK},
     title = {Improved upper bounds for nearly antipodal chromatic number of paths},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {27},
     year = {2007},
     pages = {159-174},
     zbl = {1138.05027},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1352}
}

Yu-Fa Shen; Guo-Ping Zheng; Wen-Jie HeK. Improved upper bounds for nearly antipodal chromatic number of paths. Discussiones Mathematicae Graph Theory, Tome 27 (2007) pp. 159-174. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1352/

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

[001] [2] G. Chartrand, D. Erwin and P. Zhang, A graph labeling problem suggested by FM channel restrictions, Bull. Inst. Combin. Appl. 43 (2005) 43-57. | Zbl 1066.05125

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

[003] [4] G. Chartrand, L. Nebeský and P. Zhang, Radio k-colorings of paths, Discuss. Math. Graph Theory 24 (2004) 5-21, doi: 10.7151/dmgt.1209. | Zbl 1056.05053

[004] [5] D. Fotakis, G. Pantziou, G. Pentaris and P. Spirakis, Frequency assignment in mobile and radio networks, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 45 (1999) 73-90. | Zbl 0929.68005

[005] [6] R. Khennoufa and O. Togni, A note on radio antipodal colorings of paths, Math. Bohem. 130 (2005) 277-282. | Zbl 1110.05033

[006] [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 | Zbl 0930.05087