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

He Chen ; Xueliang Li

The electronic journal of combinatorics, Tome 14 (2007)

Résumé

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 $CN(v)$ denote the color neighborhood of a vertex $v$ of $G$. In a previous paper, we showed that if $|CN(u)\cup CN(v)|\geq 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 $\lfloor{2s+4\over5}\rfloor$. In the present paper, we prove that $G$ has a heterochromatic path of length at least $\lceil{s+1\over2}\rceil$, and give examples to show that the lower bound is best possible in some sense.

Détail

DOI : 10.37236/995

Classification : 05C38, 05C15
Mots-clés : edge coloring, heterochromatic path, color neighborhood