Color degree and color neighborhood union conditions for long heterochromatic paths in edge-colored graphs

Abstract

Let $G$ be an edge-colored graph. A heterochromatic (rainbow, or multicolored) path of $G$ is such a path in which no two edges have the same color. Let $d^c(v)$ denote the color degree and $CN(v)$ denote the color neighborhood of a vertex $v$ of $G$. In a previous paper, we showed that if $d^c(v)\ge k$ (color degree condition) for every vertex $v$ of $G$, then $G$ has a heterochromatic path of length at least $\lceil \frac{k+1}{2}\rceil$, and if $|CN(u)\cup CN(v)|\ge s$ (color neighborhood union condition) for every pair of vertices $u$ and $v$ of $G$, then $G$ has a heterochromatic path of length at least $\lceil \frac{s}{3}\rceil +1$. Later, in another paper we first showed that if $k\le 7$, $G$ has a heterochromatic path of length at least $k-1$, and then, based on this we use induction on $k$ and showed that if $k\ge 8$, then $G$ has a heterochromatic path of length at least $\lceil \frac{3k}{5}\rceil +1$. In the present paper, by using a simpler approach we further improve the result by showing that if $k\ge 8$, $G$ has a heterochromatic path of length at least $\lceil \frac{2k}{3}\rceil +1$, which confirms a conjecture by Saito. We also improve a previous result by showing that under the color neighborhood union condition, $G$ has a heterochromatic path of length at least $\lfloor \frac{2s+4}{5}\rfloor$.

12 pages