1-树与外平面图的无圈边着色  

Acyclic Edge Coloring of 1-Tree and Outerplane Graphs

作　　者：许振宇[1] 

机构地区：[1]济南大学理学院,山东济南250022

出　　处：《山东科技大学学报（自然科学版）》2004年第3期95-97,共3页Journal of Shandong University of Science and Technology(Natural Science)

摘　　要：设f是图G的一个正常边着色,若在f下G中没有2 色圈,则称f是图G的一个无圈边着色,其所用最小色数为G的无圈边色数。N.Alon猜想对所有简单图,无圈边色数不超过其最大度加2。本文证明了该猜想对1 树与外平面图成立,且它们的色数均不超过最大度加1。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.This paper proved that the conjecture holds for 1-tree and outerplane graphs, whose acyclic edge chromatic numbers do not exceed △+1 .

关 键 词：图 无圈边着色 无圈边色数 1-树 外平面图 

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