Halin图的无圈边着色  

Acyclic Edge Colorings of Halin Graphs

作　　者：许振宇[1] 陈东灵[2] 穆勇[1] 

机构地区：[1]济南大学理学院,山东济南250022 [2]山东科技大学信息科学与工程学院,山东泰安271019

出　　处：《山东科技大学学报（自然科学版）》2006年第2期102-105,共4页Journal of Shandong University of Science and Technology(Natural Science)

摘　　要：设f是图G的一个正常边着色,若在f下G中没有2-色圈,则称f是图G的一个无圈边着色,其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图,无圈边色数不超过其最大度加2。本文证明了该猜想对Halin图成立,且当△≤4时,其色数不超过5；当△≥5时,其色数等于最大度。A proper edge coloring 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. N. Alon conjectured that a＇ （G） ≤Δ ＋ 2 for all graphs G, where Δ is the maximum degree in G. The paper proved that G is a Halin graph, and a＇（ G）≤Δ ＋ 5, if Δ≤4, and a＇（G） = Δ, if Δ≥5.

关 键 词：图论 图着色 无圈边着色 无圈边色数 HALIN图 

分 类 号：O157.5[理学—数学]