Acyclic edge coloring of sparse graphs
Acyclic edge coloring of sparse graphs
复制标题
DOI：
10.1016/j.disc.2012.08.012
复制
发表时间：
2012-12
期刊：
影响因子：
--
通讯作者：
Yingqian Wang;Ping Sheng
中科院分区：
文献类型：
--
作者：
Yingqian Wang;Ping Sheng
设Δ表示图的最大度。Fiamčík首先，Alon，Sudakov和Zaks后来证明了每个图都是非圈边（Δ+2）-可着色的。本文对最大平均度小于4的图证明了这个猜想。作为推论，无三角形平面图是无圈边（Δ+2）-可着色的。
Let Δ denote the maximum degree of a graph. Fiamčík first, Alon, Sudakov and Zaks later conjectured that every graph is acyclically edge (Δ+2)-colorable. In this paper, we prove this conjecture for graphs with maximum average degree less than 4. As a corollary, triangle-free planar graphs are acyclically edge (Δ+2)-colorable.