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

Summary: 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.