Acyclic edge colorings of graphs
Acyclic edge colorings of graphs
复制标题
DOI：
10.1002/jgt.1010
复制
发表时间：
2001-07
影响因子：
0.9
通讯作者：
N. Alon;B. Sudakov;A. Zaks
中科院分区：
文献类型：
--
作者：
N. Alon;B. Sudakov;A. Zaks
图G的边的正常染色称为无圈的，如果G中不存在2色圈。图G的无圈边色数记为a′（G），是图G的无圈边染色中的最少颜色数。对于某些图G，a′（G）≥ Δ（G）+ 2，其中Δ（G）是G的最大度.已知对任意图G，a′（G）≤ 16 Δ（G）.证明了存在一个常数c使得a′（G）≤ Δ（G）+ 2，并且猜想a′（G）的这个上界对所有图G都成立.我们还证明了几乎所有的Δ-正则图的a′（G）≤ Δ + 2。John Wiley & Sons，Inc. J Graph Theory 37：157-167，2001
A proper coloring of the edges of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. For certain graphs G, a′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ 16 Δ(G) for any graph G. We prove that there exists a constant c such that a′(G) ≤ Δ(G) + 2 for any graph G whose girth is at least cΔ(G) log Δ(G), and conjecture that this upper bound for a′(G) holds for all graphs G. We also show that a′(G) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001