Color Neighborhood Union Conditions for Long Heterochromatic Paths in Edge-Colored Graphs
Color Neighborhood Union Conditions for Long Heterochromatic Paths in Edge-Colored Graphs
复制标题
DOI：
10.37236/995
复制
发表时间：
2007-11
期刊：
影响因子：
--
通讯作者：
He Chen;Xueliang Li
中科院分区：
文献类型：
--
作者：
He Chen;Xueliang Li
设$G$为边色图。一条异色（彩虹或多色）路径$G$是这样一条路径，其中没有两个边缘具有相同的颜色。设$CN(v)$表示$G$的顶点$v$的颜色邻域。在之前的一篇论文中，我们证明了对于$G$的每一对顶点$u$和$v$，如果$|CN(u)\cup CN(v)|\geq s$（颜色邻域联合条件），则$G$至少有一条长度为$\lfloor{2s+4\over5}\rfloor$的异色路径。本文证明了$G$具有一条长度至少为$\lceil{s+1\over2}\rceil$的异色路径，并给出了在某种意义上下界是最佳可能的例子。
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.