\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
\nopagenumbers
\noindent
%
%
{\bf He Chen and Xueliang Li}
%
%
\medskip
\noindent
%
%
{\bf Long Heterochromatic Paths in Edge-Colored Graphs }
%
%
\vskip 5mm
\noindent
%
%
%
%
Let $G$ be an edge-colored graph. A heterochromatic path of $G$ is
such a path in which no two edges have the same color. $d^c(v)$
denotes the color degree of a vertex $v$ of $G$. In a previous paper,
we showed that if $d^c(v)\geq k$ for every vertex $v$ of $G$, then $G$
has a heterochromatic path of length at least $\lceil{k+1\over
2}\rceil$. It is easy to see that if $k=1,2$, $G$ has a
heterochromatic path of length at least $k$. Saito conjectured that
under the color degree condition $G$ has a heterochromatic path of
length at least $\lceil{2k+1\over 3}\rceil$. Even if this is true, no
one knows if it is a best possible lower bound. Although we cannot
prove Saito's conjecture, we can show in this paper that if $3\leq
k\leq 7$, $G$ has a heterochromatic path of length at least $k-1,$ and
if $k\geq 8$, $G$ has a heterochromatic path of length at least
$\lceil{3k\over 5}\rceil+1$. Actually, we can show that for $1\leq
k\leq 5$ any graph $G$ under the color degree condition has a
heterochromatic path of length at least $k$, with only one exceptional
graph $K_4$ for $k=3$, one exceptional graph for $k=4$ and three
exceptional graphs for $k=5$, for which $G$ has a heterochromatic path
of length at least $k-1$. Our experience suggests us to conjecture
that under the color degree condition $G$ has a heterochromatic path
of length at least $k-1$.

\bye

.
