For paths Pₙ, G. Chartrand, L. Nebeský and P. Zhang showed that $a{c}^{\text{'}}\left(Pₙ\right)\le \left(\genfrac{}{}{0pt}{}{n-2}{2}\right)+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}^{\text{'}}\left(Pₙ\right)\le \left(\genfrac{}{}{0pt}{}{n-2}{2}\right)-n/2-⎣10/n⎦+7$ if n is even positive integer and n ≥ 10, and $a{c}^{\text{'}}\left(Pₙ\right)\le \left(\genfrac{}{}{0pt}{}{n-2}{2}\right)-(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ₙ.

The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph $(V,E_N)$ where $E_N$ = a,b | a ≠ b, x,a ∈ E and x,b ∈ E for some x ∈ V. It is well-known that the neighborhood graph N(G) is connected if and only if the graph G is connected and non-bipartite. We present some results concerning the k-iterated neighborhood graph $N^k\left(G\right):=N\left(N(...N\left(G\right))\right)$ of G. In particular we investigate conditions for G and k such that $N^k\left(G\right)$ becomes a complete graph.