\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}

\begin{document}
\noindent
%
%
{\bf Meysam Alishahi, Ali Taherkhani, and Carsten Thomassen}
%
%

\medskip
\noindent
%
%
{\bf Rainbow Paths with Prescribed Ends}
%
%

\vskip 5mm
\noindent
%
%
%
%
It was conjectured in [S. Akbari, F. Khaghanpoor, and
S. Moazzeni. Colorful paths in vertex coloring of graphs. Preprint]
that, if $G$ is a connected graph distinct from $C_7$, then there is a
$\chi(G)$-coloring of $G$ in which every vertex $v\in V(G)$ is an
initial vertex of a path $P$ with $\chi(G)$ vertices whose colors are
different. In [S. Akbari, V. Liaghat, and A. Nikzad. Colorful paths in
vertex coloring of graphs.  Electron. J. Combin. 18(1): P17, 9pp,
2011] this was proved with $\lfloor\frac{\chi(G)}{2} \rfloor $
vertices instead of $\chi(G)$ vertices. We strengthen this to
$\chi(G)-1$ vertices. We also prove that every connected graph with at
least one edge has a proper $k$-coloring (for some $k$) such that
every vertex of color $i$ has a neighbor of color $i+1$ ({\rm mod}
$k$). $C_5$ shows that $k$ may have to be greater than the chromatic
number. However, if the graph is connected, infinite and locally
finite, and has finite chromatic number, then the $k$-coloring exists
for every $k \geq \chi(G)$. In fact, the $k$-coloring can be chosen
such that every vertex is a starting vertex of an infinite path such
that the color increases by $1$ ({\rm mod} $k$) along each edge. The
method is based on the circular chromatic number $\chi_c(G)$. In
particular, we verify the above conjecture for all connected graphs
whose circular chromatic number equals the chromatic number.



\end{document}