Acyclic edge colorings of planar graphs and seriesparallel graphs
Acyclic edge colorings of planar graphs and seriesparallel graphs
复制标题
DOI：
10.1007/s11425-008-0124-x
复制
发表时间：
2009-03
期刊：
影响因子：
--
通讯作者：
Jianfeng Hou;Jian-Liang Wu;G. Liu;B. Liu
中科院分区：
文献类型：
--
作者：
Jianfeng Hou;Jian-Liang Wu;G. Liu;B. Liu
如果图G中不存在2-色圈，则称图G的正常边染色是无圈的。图G的无圈边色数记为a ′（G），是图G的无圈边染色中的最少颜色数。Alon等证明了对任意图都有ata ′（G）<$Δ（G）+2.对围长为g（G）的平面图G，证明了当g（G）<$3时，a ′（G）<$max{2Δ（G）− 2，Δ（G）+22}，当g（G）<$5时，a ′（G）<$Δ（G）+2，当g（G）<$7时，a ′（G）<$Δ（G）+1，当g（G）<$16，Δ（G）<$3时，a ′（G）= Δ（G）.对于串-平行图G，我们有a ′（G）<$Δ（G）+ 1.
A proper edge coloring of a graphGis called acyclic if there is no 2-colored cycle inG. The acyclic edge chromatic number ofG, denoted bya′(G), is the least number of colors in an acyclic edge coloring ofG. Alon et al. conjectured thata′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphsGwith girthg(G), we prove thata′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} ifg(G) ⩾ 3,a′(G) ⩽ Δ(G) + 2 ifg(G) ⩾ 5,a′(G) ⩽ Δ(G) + 1 ifg(G) ⩾ 7, anda′(G) = Δ(G) ifg(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphsG, we havea′(G) ⩽ Δ(G) + 1.