Acyclic edge coloring of graphs
Acyclic edge coloring of graphs
复制标题
图的非循环边缘着色
DOI：
10.1016/j.dam.2013.12.001
复制
发表时间：
2013-02
影响因子：
1.1
通讯作者：
Yaqiong Zhang
中科院分区：
文献类型：
--
作者：
Tao Wang;Yaqiong Zhang
图G的无环边着色是一种适当的边着色，使得由任意两个颜色类诱导的子图是线性森林（最大度最多为2的无环图）。图G的无环着色指数χ a′(G)是G的无环边着色所需的最少色数。Fiamčík（1978）推测χ a′(G)≤Δ (G)+ 2，其中Δ (G)是G的最大度。这个猜想被称为无环边着色猜想（AECC）。对于G的每个适当子图H，如果χ A ' (G)> κ且χ A ' (H)≤κ，则最大程度为κ的图G为κ-缺失最小。本文的目的是提供关于κ-缺失最小图的许多结构引理。利用结构引理，首先证明了最大平均度小于4的图的AECC成立（定理4.3）。其次，我们证明了AECC在不含三角形的平面图形中成立，且每5个环中最多有3条边包含在三角形中（定理4.4），由此我们可以得出一些已知的结果作为推论。第三，证明了无相交三角形的平面图G满足χ a ' (G)≤Δ (G)+ 3（定理4.6）。最后，我们考虑一个极端情况并证明：如果G是一个Δ (G)≥3且所有3+顶点都是独立的图，则χ a ' (G)= Δ (G)。我们希望这些结构引理能对非环边着色问题有所启发。
An acyclic edge coloring of a graph G is a proper edge coloring such that the subgraph induced by any two color classes is a linear forest (an acyclic graph with maximum degree at most two). The acyclic chromatic index χ a′(G) of a graph G is the least number of colors needed in an acyclic edge coloring of G. Fiamčík (1978) conjectured that χ a′(G)≤ Δ (G)+ 2, where Δ (G) is the maximum degree of G. This conjecture is well known as the Acyclic Edge Coloring Conjecture (AECC). A graph G with maximum degree at most κ is κ-deletion-minimal if χ a′(G)> κ and χ a′(H)≤ κ for every proper subgraph H of G. The purpose of this paper is to provide many structural lemmas on κ-deletion-minimal graphs. By using the structural lemmas, we firstly prove that AECC is true for the graphs with maximum average degree less than four (Theorem 4.3). We secondly prove that AECC is true for the planar graphs without triangles adjacent to cycles of length at most four, with an additional condition that every 5-cycle has at most three edges contained in triangles (Theorem 4.4), from which we can conclude some known results as corollaries. We thirdly prove that every planar graph G without intersecting triangles satisfies χ a′(G)≤ Δ (G)+ 3 (Theorem 4.6). Finally, we consider one extreme case and prove it: if G is a graph with Δ (G)≥ 3 and all the 3+-vertices are independent, then χ a′(G)= Δ (G). We hope the structural lemmas will shed some light on the acyclic edge coloring problems.
登录
查看更多内容
DOI：
10.1016/j.disc.2012.08.012
发表时间：
2012-12
期刊：
Discret. Math.
影响因子：
--
作者：
Yingqian Wang;Ping Sheng
通讯作者：
Yingqian Wang;Ping Sheng
DOI：
10.1016/j.disc.2009.06.007
发表时间：
2010-05
期刊：
Discret. Math.
影响因子：
--
作者：
M. Borowiecki;A. Fiedorowicz
通讯作者：
M. Borowiecki;A. Fiedorowicz
DOI：
10.1016/j.ejc.2013.02.007
发表时间：
2012-06
期刊：
Eur. J. Comb.
影响因子：
--
作者：
Louis Esperet;Aline Parreau
通讯作者：
Louis Esperet;Aline Parreau
DOI：
10.1007/s11425-008-0124-x
发表时间：
2009-03
期刊：
Science in China Series A: Mathematics
影响因子：
--
作者：
Jianfeng Hou;Jian-Liang Wu;G. Liu;B. Liu
通讯作者：
Jianfeng Hou;Jian-Liang Wu;G. Liu;B. Liu
影响因子：
0.8
作者：
Manu Basavaraju;S. Chandran;Nathann Cohen;F. Havet;Tobias Müller
通讯作者：
Manu Basavaraju;S. Chandran;Nathann Cohen;F. Havet;Tobias Müller