PDF全文下载：2011020208
张埂， 吴树猛， 焦娇
（中国矿业大学 理学院，江苏 徐州 221008）
摘要: 如果图G的正常边染色不包含2-色圈,则称它是图G的无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ（G）+2,其中Δ（G）为图G的最大顶点度。已经证明了当Δ≤3时,此猜想成立。本研究利用线性-时间算法思想研究了最大顶点度为4的图，并给出了最大顶点度为4的图G满足此猜想的一个充分条件为图G的任意2个最大度顶点都不邻接。
关键词：图; 无圈边染色; 无圈边色数
中图分类号: O 157.5 文献标志码： Ａ
Acyclic Edge Coloring of Graphs with Maximum Degree 4
ZHANG Geng, WU Shu-meng, JIAO Jiao
（College of Science,China University of Mining and Technology,Xuzhou 221008,China）
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. 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. This conjecture has been verified to be true when Δ≤3. In this paper,by using linear-time algorithm,we study the graphs with maximum degree 4 and prove the conjecture also hold when no two vertices of degree 4 in G are adjacent.
Key words: graphs; acyclic edge coloring; acyclic chromatic number
收稿日期：2010-07-22
作者简介： 张埂（1986—），男，硕士研究生.
