Discussiones Mathematicae Graph Theory 27(1) (2007)
159-174
DOI: https://doi.org/10.7151/dmgt.1352
IMPROVED UPPER BOUNDS FOR NEARLY ANTIPODAL CHROMATIC NUMBER OF PATHS
Yu-Fa Shena, Guo-Ping Zhenga, Wen-Jie Heb
aDepartment of Mathematics and Physics
Hebei Normal University of Science and Technology
Qinhuangdao 066004, P.R. China
bApplied Mathematics Institute
Hebei University of Technology
Tianjin 300130, P.R. China
e-mail: syf030514@163.com (Yu-Fa Shen).
Abstract
For paths Pn, G. Chartrand, L. Nebeský and P. Zhang showed that ac′(Pn) ≤ (n-2)(n-3)/2+2 for every positive integer n, where ac′(Pn) denotes the nearly antipodal chromatic number of Pn. In this paper we show that ac′(Pn) ≤ (n-2)(n-3)/2−[n/2]− ⎣10/n⎦+7 if n is even positive integer and n ≥ 10, and ac′(Pn) ≤ (n-2)(n-3)/2−[(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 Pn.Keywords: radio colorings, nearly antipodal chromatic number, paths.
2000 Mathematics Subject Classification: 05C12, 05C15, 05C78.
References
[1] | G. Chartrand, D. Erwin, F. Harary and P. Zhang, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33 (2001) 77-85. |
[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. |
[3] | G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of graphs, Math. Bohem. 127 (2002) 57-69. |
[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. |
[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. |
[6] | R. Khennoufa and O. Togni, A note on radio antipodal colorings of paths, Math. Bohem. 130 (2005) 277-282. |
[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. |
Received 21 February 2006
Revised 31 October 2006
Close