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

\begin{document}
\noindent
%
%
{\bf Saieed Akbari, Vahid Liaghat and Afshin Nikzad}
%
%

\medskip
\noindent
%
%
{\bf Colorful Paths in Vertex Coloring of Graphs}
%
%

\vskip 5mm
\noindent
%
%
%
%
\newcommand{\cpath}[1]{$#1$-{colorful path}}%
A colorful path in a graph $G$ is a path with $\chi(G)$ vertices whose
colors are different. A \cpath{v} is such a path, starting from
$v$. Let $G\neq C_7$ be a connected graph with maximum degree
$\Delta(G)$. We show that there exists a $(\Delta(G)+1)$-coloring of
$G$ with a \cpath{v} for every $v\in V(G)$. We also prove that this
result is true if one replaces $(\Delta(G)+1)$ colors with $2\chi(G)$
colors. If $\chi(G)=\omega(G)$, then the result still holds for
$\chi(G)$ colors. For every graph $G$, we show that there exists a
$\chi(G)$-coloring of $G$ with a rainbow path of length
$\lfloor\chi(G)/2\rfloor$ starting from each $v \in V(G)$.


\end{document}

.
