Improved Upper Bounds for Nearly Antipodal Chromatic Number of Paths

Yufa Shen1, Wenjie He 2, and Guoping Zheng 1
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     Full Text  PDF

For paths $P_{n}$, G. Chartrand, L. Nebesk\'{y} and P. Zhang showed that ac$'(P_{n})\leq\binom{n-2}{2}+2$ for every positive integer $n$, where ac$'(P_{n})$ denotes the nearly antipodal chromatic number of $P_{n}$. In this paper we show that ac$'(P_{n})\leq\binom{n-2}{2}-\frac{n}{2}-\lfloor\frac{10}{n}\rfloor+7$ if $n$ is even positive integer and $n\geq10$, and ac$'(P_{n})\leq\binom{n-2}{2}-\frac{n-1}{2}-\lfloor\frac{13}{n}\rfloor+8$ if $n$ is odd positive integer and $n\geq13$. For all even positive integers $n\geq10$ and all odd positive integers $n\geq13$, these results improve the upper bounds for nearly antipodal chromatic number of $P_{n}$.