图的围长与无圈边色数之间的关系

对于一个图G的正常边着色，如果此种边着色使得该图没有2—色的圈，那么这种边着色被称为是G的无圈边着色．用d(G)表示图G的无圈边色数，即G的无圈边着色中所使用的最小颜色数．Alon N，Sadakov B and Zaks A在1]中有如下结果：对于围长至少是2000△(G)log△(G)的图G，有d(G)≤△ 2，其中△是图G的最大度．我们改进了这个结果，得到了如下结论：对于围长至少是700△(G)log△(G)的图G，有d(G)≤△ 2．

Relationship Between Girth and Acyclic Edge Chromatic Number of Graph

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 1]). We improve the result and prove that α′(G)Δ+2 for any graph G whose girth is at least 700Δ(G)logΔ(G).