Long Heterochromatic Paths in Edge-Colored Graphs

He Chen and Xueliang Li
Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, P. R. China

Abstract     Full Text  PDF

For an edge-colored graph $G$, a heterochromatic subgraph of $G$ is such a subgraph 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 this talk, we consider the long heterochromatic paths in an edge-colored graph $G$ under the condition when $d^c(v)\geq k$ for any $v$ of $G$ or when $|CN(u)\cup CN(v)|\geq s$ for every pair of vertices $u$ and $v$ of $G$.