边染色图中的正常染色的路和圈

J4 ›› 2012, Vol. 47 ›› Issue (6): 63-66.

边染色图中的正常染色的路和圈

宋宝阳,王晓宗,任宇屏

山东大学数学学院, 山东济南 250100

收稿日期:2011-05-03 出版日期:2012-06-20 发布日期:2012-06-26
作者简介:宋宝阳(1990- ),男,研究方向为图论.Email:songbaoyang@mail.sdu.edu.cn
基金资助:
国家自然科学基金资助项目(11101234)

Properly colored paths and cycles in edge colored graphs

SONG Bao-yang, WANG Xiao-zong, REN Yu-ping

School of Mathematics, Shandong University, Jinan 250100, Shandong, China

Received:2011-05-03 Online:2012-06-20 Published:2012-06-26

摘要/Abstract

摘要：

讨论了无三角形的边染色图中的正常染色的路和圈, 在无三角形图中改进了原有的结果。证明了在顶点的最小色度至少为d (d≥2)的条件下, 边染色图G或者存在长至少为4d-2的正常染色的路, 或者存在长至少为2「2d／3的正常染色的圈。

关键词: 边染色图;色度;正常染色的路;正常染色的圈

Abstract:

Properly colored paths and cycles in edge colored triangle-free graphs are discussed, and the known result is improved in triangle-free graphs. It is proved that in any edge colored triangle-free graph G with color degree at least d(d≥2), there exists either a properly colored path of size at least 4d-2, or a properly colored cycle of size at least 2「2d3.

Key words: edge colored graph; color degree; properly colored path; properly colored cycle

宋宝阳,王晓宗,任宇屏. 边染色图中的正常染色的路和圈[J]. J4, 2012, 47(6): 63-66.

SONG Bao-yang, WANG Xiao-zong, REN Yu-ping. Properly colored paths and cycles in edge colored graphs[J]. J4, 2012, 47(6): 63-66.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed