| 不含3圈的平面图的无圈边染色 |
| |
| 引用本文： | 张江,张埂. 不含3圈的平面图的无圈边染色[J]. 贵州大学学报(自然科学版), 2013, 0(5): 9-12 |
| |
| 作者姓名： | 张江 张埂 |
| |
| 作者单位： | [1]西南交通大学牵引动力国家重点实验室,四川成都610031 [2]重庆大学自动化学院,重庆400030 |
| |
| 基金项目： | 中央高校基本科研业务费专项基金（LK0103） |
| |
| 摘 要： | 图的无圈边染色是图的染色理论中的一个重要问题，2001年，Alon等猜想任意简单图G的无圈边色数都不超过△（G）＋2，其中△（G）为图G的最大顶点度。为了研究该猜想对平面图是否成立，利用差值转移方法，证明了不包含三角形的平面图G的无圈边色数不超过△（G）＋3．
|
| 关 键 词： | 无圈边染色 无圈边色数 平面图 差值转移法 |
Acyclic Edge Coloring of Planar Graphs without 3 Cycles |
| |
| ZHANG Jiang,ZHANG Geng. Acyclic Edge Coloring of Planar Graphs without 3 Cycles[J]. Journal of Guizhou University(Natural Science), 2013, 0(5): 9-12 |
| |
| Authors: | ZHANG Jiang ZHANG Geng |
| |
| Affiliation: | 1. Traction Power State Key Laboratory of Southwest Jiaotong University, Chengdu 610031, China; 2. School of Automation, Chongqing University, Chongqing 400030, China) |
| |
| Abstract: | One of the main subjects of coloring theory of graph is acyclic edge coloring. In 2001, Alon et al. conjectured that the acyclic chromatic number of any simple graph G is no more than △ （G） ＋ 2 , where △ （G） is the maximum degree of G. In order to prove the conjecture is true for planar graphs, in this paper, we proved that the acyclic chromatic number of planar graphs without 3 cycles is no more than △ （G） ＋ 3 with discharging method. |
| |
| Keywords: | acyclic edge coloring acyclic chromatic number planar graphs discharging method |
| 本文献已被 维普 等数据库收录！ |
|
