Improved upper bounds for nearly antipodal chromatic number of paths

Yu-Fa Shen; Guo-Ping Zheng; Wen-Jie HeK

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 1, page 159-174
  • ISSN: 2083-5892

Abstract

top
For paths Pₙ, G. Chartrand, L. Nebeský and P. Zhang showed that a c ' ( P ) 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 a c ' ( P ) n - 2 2 - n / 2 - 10 / n + 7 if n is even positive integer and n ≥ 10, and a c ' ( P ) 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ₙ.

How to cite

top

Yu-Fa Shen, Guo-Ping Zheng, and Wen-Jie HeK. "Improved upper bounds for nearly antipodal chromatic number of paths." Discussiones Mathematicae Graph Theory 27.1 (2007): 159-174. <http://eudml.org/doc/270297>.

@article{Yu2007,
abstract = {For paths Pₙ, G. Chartrand, L. Nebeský and P. Zhang showed that $ac^\{\prime \}(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^\{\prime \}(Pₙ) ≤ \binom\{n-2\}\{2\} - n/2 - ⎣10/n⎦ + 7$ if n is even positive integer and n ≥ 10, and $ac^\{\prime \}(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ₙ.},
author = {Yu-Fa Shen, Guo-Ping Zheng, Wen-Jie HeK},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {radio colorings; nearly antipodal chromatic number; paths; bounds},
language = {eng},
number = {1},
pages = {159-174},
title = {Improved upper bounds for nearly antipodal chromatic number of paths},
url = {http://eudml.org/doc/270297},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Yu-Fa Shen
AU - Guo-Ping Zheng
AU - Wen-Jie HeK
TI - Improved upper bounds for nearly antipodal chromatic number of paths
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 1
SP - 159
EP - 174
AB - For paths Pₙ, G. Chartrand, L. Nebeský and P. Zhang showed that $ac^{\prime }(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^{\prime }(Pₙ) ≤ \binom{n-2}{2} - n/2 - ⎣10/n⎦ + 7$ if n is even positive integer and n ≥ 10, and $ac^{\prime }(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ₙ.
LA - eng
KW - radio colorings; nearly antipodal chromatic number; paths; bounds
UR - http://eudml.org/doc/270297
ER -

References

top
  1. [1] G. Chartrand, D. Erwin, F. Harary and P. Zhang, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33 (2001) 77-85. Zbl0989.05102
  2. [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. Zbl1066.05125
  3. [3] G. Chartrand, D. Erwin and P. Zhang, Radio antipodal colorings of graphs, Math. Bohem. 127 (2002) 57-69. Zbl0995.05056
  4. [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. Zbl1056.05053
  5. [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. Zbl0929.68005
  6. [6] R. Khennoufa and O. Togni, A note on radio antipodal colorings of paths, Math. Bohem. 130 (2005) 277-282. Zbl1110.05033
  7. [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 Zbl0930.05087

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.