不含4圈的平面图的无圈边染色

J4 ›› 2012, Vol. 47 ›› Issue (6): 76-79.

不含4圈的平面图的无圈边染色

丁伟

中国矿业大学理学院, 江苏徐州 221008

收稿日期:2011-03-21 出版日期:2012-06-20 发布日期:2012-06-26
作者简介:丁伟(1986- ),男,硕士研究生,研究方向为图论及其应用.Email:dingweiyaoming@yahoo.cn
基金资助:
中央高校基本科研业务费专项基金(2010LKSX06);国家自然科学基金资助项目(NSFC11001265)

Acyclic edge coloring of planar graphs without 4-Cycles

DING Wei

College of Science, China University of Mining and Technology, Xuzhou 221008, Jiangsu, China

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

摘要/Abstract

摘要：

如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数。利用已有的关于平面图的结构性质,证明了不含4圈的2-连通平面图的无圈边色数不超过Δ(G)+11。

关键词: 无圈边染色;平面图;围长

Abstract:

If a proper edge coloring of G contains no bichromatic cycles in G, then it is an acyclic edge coloring of G. The acyclic chromatic number of G is the minimum number of colors among all the acyclic edge colorings of G. By using the properties of planar graphs that have been proposed, it is proved that if G is a 2-connected planar graph without 4-cycles, then its acyclic chromatic number is no more than Δ(G)+11.

Key words: acyclic edge coloring; planar graph; girth

丁伟. 不含4圈的平面图的无圈边染色[J]. J4, 2012, 47(6): 76-79.

DING Wei. Acyclic edge coloring of planar graphs without 4-Cycles[J]. J4, 2012, 47(6): 76-79.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed