Improved upper bounds for nearly antipodal chromatic number of paths

• Autorzy: Yu-Fa Shen , Guo-Ping Zheng , Wen-Jie HeK
• Języki publikacji: EN

Abstrakty

EN

For paths Pₙ, G. Chartrand, L. Nebeský and P. Zhang showed that $ac'(Pₙ) ≤ \binom{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ₙ) ≤ \binom{n-2}{2} - n/2 - ⎣10/n⎦ + 7$ if n is even positive integer and n ≥ 10, and $ac'(Pₙ) ≤ \binom{n-2}{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 Pₙ.

Słowa kluczowe

EN

radio colorings; nearly antipodal chromatic number; paths

Kategorie tematyczne

• 05C12: Distance in graphs
• 05C15: Coloring of graphs and hypergraphs
• 05C78: Graph labelling (graceful graphs, bandwidth, etc.)

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2007
• Tom: 27
• Numer: 1
• Strony: 159-174

Daty

wydano

2007

otrzymano

2006-02-21

poprawiono

2006-10-31

Twórcy

autor

Yu-Fa Shen

• Department of Mathematics and Physics, Hebei Normal University of Science and Technology, Qinhuangdao 066004, P.R. China

autor

Guo-Ping Zheng

• Department of Mathematics and Physics, Hebei Normal University of Science and Technology, Qinhuangdao 066004, P.R. China

autor

Wen-Jie HeK

• Applied Mathematics Institute, Hebei University of Technology, Tianjin 300130, P.R. China

Bibliografia

• [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

Identyfikatory

DOI

10.7151/dmgt.1352