图的围长与无圈边色数之间的关系(英文)

Relationship Between Girth and Acyclic Edge Chromatic Number of Graph

对于一个图G的正常边着色 ,如果此种边着色使得该图没有 2 色的圈 ,那么这种边着色被称为是G的无圈边着色 .用α′(G)表示图G的无圈边色数 ,即G的无圈边着色中所使用的最小颜色数 .AlonN ,SadakovBandZaksA在 [1]中有如下结果 :对于围长至少是 2 0 0 0Δ(G)logΔ(G)的图G ,有α′(G) Δ+ 2 ,其中Δ是图G的最大度 .我们改进了这个结果 ,得到了如下结论 :对于围长至少是 70 0Δ(G)logΔ(G)的图G ,有α′(G) Δ+

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 α′(G) is the least number of colors in an acyclic edge coloring of G. It is known that α′(G)Δ+2 for any graph whose girth is at least 2000Δ(G)logΔ(G) where Δ(G) is the maximum degree in G (see ). We improve the result and prove that α′(G)Δ+2 for any graph G whose girth is at least 700Δ(G)logΔ(G).