-
77浏览
-
0点赞
-
0收藏
-
0分享
-
108下载
-
0评论
-
引用
期刊论文
Long heterochromatic paths in edge-colored graphs
,-0001,():
Let G be an edge-colored graph. A heterochromatic path of G is such a path in which no two edges have the same color, de(v) denotes the color degree of a vertex v of G. In a previous paper, we showed that if dC(v)≥k for every vertex v of G, then G has a heterochromatic path of length at least [k+1/2]. It is easy to see that if k=1, 2, G has a heterochromatic path of length at least k. Saito conjectured that under the color degree condition G has a heterochromatic path of length at least [2k+1/3]. Even if this is true, no one knows if it is a best possible lower bound. Although we cannot prove Saito's conjecture, we can show in this paper that if 3≤k≤7, G has a heterochromatic path of length at least k-1, and if k≥8, G has a heterochromatic path of length at least [3k/5]+1. Actually, we can show" that for 1≤k≤5 any graph G under the color degree condition has a heterochromatic path of length at least k, with only one exceptional graph K4 for k=3, one exceptional graph for k=4 and three exceptional graphs for k=5, for which G has a heterochromatic path of length at least k-1. Our experience suggests us to conjecture that under the color degree condition G has a heterochromatic path of length at least k-1.
【免责声明】以下全部内容由[李学良]上传于[2006年02月14日 23时21分39秒],版权归原创者所有。本文仅代表作者本人观点,与本网站无关。本网站对文中陈述、观点判断保持中立,不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考,并请自行承担全部责任。
本学者其他成果
同领域成果