论文部分内容阅读
图G=(V,E)的边着色是一个映射c：E→S,其中S(?)N是颜色集合.(G,c)称为一个边着色图.如果H是G的一个子图,并且对于任意不同的两条边e,f∈E(H),c(e)≠c(f),则称(H,c)是(G,c)的一个彩虹子图.给定边着色图(G,c),对v∈V,将(G,c)中与v关联的所有边上不同颜色的个数称为v在(G,c)中的色度,记作D(v),(G,c)的最大色度和最小色度分别记作△(G)和3(G).在边着色图(G,c)中,边上的颜色都不相同的匹配称为彩虹匹配；用于覆盖V(G)的不相交彩虹星的集合称为彩虹控制集.将边着色图(G,c)中边上的颜色都不相同的路和圈称为彩虹路和彩虹圈.边着色图(G,c)称为彩虹连通的当且仅当对于任意的x,y∈V(G),存在一条彩虹路连接x和y.本文中,我们首先介绍了彩虹匹配和彩虹控制集的一些已知结论,然后对彩虹图进行了研究,得到了如下的一些结论：(1)给定边着色图(G,c),那么(G,c)中包含一条长度至少为[δ(G)/2]的彩虹路；(2)(G,c)中要么包含一条长度至少为[3δ(G)/4]的彩虹路,要么包含一个长度至少为[δ(G)/4]+2的彩虹圈；(3)给出了边着色单圈图是彩虹连通的若干必要条件；(4)对于n阶(n≥3)边着色图(G,c),如果3(G)≥n/2,那么边着色图(G,c)中有一个非单色哈密顿圈.该结论是对图论哈密顿圈问题中Dirac条件的推广；(5)给定n阶(n≥4)边着色图(G,c),G不是完全图,如果对于(G,c)中任意不相邻的点x和y,均有d(x)+d(y)≥n,则边着色图(G,c)中有一个非单色哈密顿圈.该结论是对图论哈密顿圈问题中Ore条件的推广；(6)在边着色二部图中对Konig定理进行了讨论.