数学研究
數學研究
수학연구
JOURNAL OF MATHEMATICAL STUDY
2003年
2期
136-139
,共4页
无圈边着色%无圈边色数%围长%概率
無圈邊著色%無圈邊色數%圍長%概率
무권변착색%무권변색수%위장%개솔
acyclic edge coloring%acyclic edge chromatic number%girth%probability
对于一个图G的正常边着色,如果此种边着色使得该图没有2-色的圈,那么这种边着色被称为是G的无圈边着色. 用α′(G)表示图G的无圈边色数,即G的无圈边着色中所使用的最小颜色数. Alon N, Sadakov B and Zaks A在[1]中有如下结果:对于围长至少是2000Δ(G)logΔ(G)的图G,有α′(G)≤Δ+2,其中Δ是图G的最大度. 我们改进了这个结果,得到了如下结论:对于围长至少是700Δ(G)logΔ(G)的图G,有α′(G)≤Δ+2.
對于一箇圖G的正常邊著色,如果此種邊著色使得該圖沒有2-色的圈,那麽這種邊著色被稱為是G的無圈邊著色. 用α′(G)錶示圖G的無圈邊色數,即G的無圈邊著色中所使用的最小顏色數. Alon N, Sadakov B and Zaks A在[1]中有如下結果:對于圍長至少是2000Δ(G)logΔ(G)的圖G,有α′(G)≤Δ+2,其中Δ是圖G的最大度. 我們改進瞭這箇結果,得到瞭如下結論:對于圍長至少是700Δ(G)logΔ(G)的圖G,有α′(G)≤Δ+2.
대우일개도G적정상변착색,여과차충변착색사득해도몰유2-색적권,나요저충변착색피칭위시G적무권변착색. 용α′(G)표시도G적무권변색수,즉G적무권변착색중소사용적최소안색수. Alon N, Sadakov B and Zaks A재[1]중유여하결과:대우위장지소시2000Δ(G)logΔ(G)적도G,유α′(G)≤Δ+2,기중Δ시도G적최대도. 아문개진료저개결과,득도료여하결론:대우위장지소시700Δ(G)logΔ(G)적도G,유α′(G)≤Δ+2.
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).
