Weijie He

Wenjie He 1, Yufa Shen 2, and Peipei Zhang 1
1 Applied Mathematics Institute, Hebei University of Technology, Tianjin 300130, P. R. China
2 Department of Mathematics and Physics, Hebei Normal University of Science and Technology, Qinhuangdao 066004, P. R. China

For a connected graph $G$ and any two vertices $u$ and $v$ in $G$, let $D(u,v)$ denote the length of a longest $u-v$ path in $G$. A \emph{hamiltonian coloring} of a connected graph $G$ of order $n$, is an assignment $c$ of colors (positive integers) to the vertices in $G$ such that $D(u,v)+|c(u)-c(v)|\geq n-1$ for every two distinct vertices $u$ and $v$ in $G$. The \emph{value} hc$(c)$ of a hamiltonian coloring $c$ is the maximum color assigned to a vertex of $G$. The \emph{hamiltonian chromatic number} hc$(G)$ of $G$ is min$\{$hc$(c)\}$ taken over all hamiltonian colorings $c$ of $G$. In this paper we present a pseudo greedy algorithm for hamiltonian coloring for $P_{n}$, and show that for all even integers $n\geq10$, hc$(P_{n})$ $\leq \binom{n-1}{2}-\frac{n}{2}-\lfloor\frac{10}{n}\rfloor+6$. For all even integer $n\geq10$, this result provides an improved upper bound for hamiltonian chromatic number of $P_{n}$, and disproves a conjecture about the antipodal chromatic number of $P_{n}$, which was given by Chartrand, Erwin and Zhang.