Pseudo Greedy Algorithm And Upper Bound For Hamiltonian Chromatic Number Of Paths

A hamiltonian coloring of a connected graph G of order n is an assignmentc of colors (positive integers) to the vertices of G, such that D(u, v) + |c(u) - c(v)|≥n- 1 for every two distinct vertices u and v of G, where D(u, v) denotes the length of a longest u - v path of G. The value hc(c) of a hamiltonian coloring c is the maximum color assigned by c to a vertex of G. The hamiltonian chromatic number hc(G) of G is the min{hc(c)} taken over all hamiltonian colorings c of G. For path P_n, Chartrand, L.Nebesky and P.Zhang have shown that hc(P_n) = ac(P_n)≤(?) + 1 for every positiveinteger n, and furthemore hc(P_n) = ac(P_n)≤(?) -n-1/2 +4 for all odd integer n≥7. In this paper, We present a pseudo greedy algorithm for hamiltonian coloring for P_n, and show that for all even integer n≥10, hc(P_n) = ac(P_n)≤(?) -n/2 - (?)10/n」+ 6. For all even integer n≥10, this result provides an improved upper bound for hamiltonian chromatic numberof P_n, and disproves a conjecture about the antipodal chromatic number of P_n, which was given by Chartrand, Erwin and Zhang.