ArticleOriginal scientific text

Title

Improved upper bounds for nearly antipodal chromatic number of paths

Authors 1, 1, 2

Affiliations

  1. Department of Mathematics and Physics, Hebei Normal University of Science and Technology, Qinhuangdao 066004, P.R. China
  2. Applied Mathematics Institute, Hebei University of Technology, Tianjin 300130, P.R. China

Abstract

For paths Pₙ, G. Chartrand, L. Nebeský and P. Zhang showed that ac(P)bom{n-2}{2}+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)bom{n-2}{2}-n2-10n+7 if n is even positive integer and n ≥ 10, and ac(P)bom{n-2}{2}-n-12-13n+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ₙ.

Keywords

radio colorings, nearly antipodal chromatic number, paths

Bibliography

  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
Pages:
159-174
Main language of publication
English
Received
2006-02-21
Accepted
2006-10-31
Published
2007
Exact and natural sciences