最大度为4的外平面图的无圈边色数  

Acyclic edge coloring of outerplanar graphs with maximum degree 4

作　　者：王艺桥[1] 舒巧君[2] 

机构地区：[1]北京中医药大学管理学院,北京100029 [2]杭州电子科技大学理学院,浙江杭州310018

出　　处：《浙江师范大学学报（自然科学版）》2014年第4期407-411,共5页Journal of Zhejiang Normal University:Natural Sciences

基　　金：国家自然科学基金资助项目(11301035);北京中医药大学卫生管理与卫生经济创新团队项目

摘　　要：一个图G的无圈边染色是一个正常的边染色,使得任一个圈上至少有3种不同的颜色.G的无圈边色数a'(G)是使得G有无圈k-边染色的最小整数k.设G是一个最大度为4的外平面图.对于现有结果 4≤a'(G)≤5中,何时为4,何时为5,还没有一个完整的刻画.给出一个使得a'(G)=4的充分条件,拓展了该领域的相关结果.An acyclic edge coloring of a graph G was named as a proper edge coloring such that there would be no bichromatic cycles produced. The acyclic chromatic index a＇（ G） of G was introduced as the smallest integer k such that G had an acyclic edge coloring by k colors. It was showed that every outerplanar graph G with Δ = 4 satisfied 4≤a＇（ G） ≤5,but there was not a fine characterization yet for such outerplanar graph G to have a＇（ G） = 4 or a＇（ G） = 5. A sufficient condition for an outerplanar graph G with Δ = 4 to have the acyclic chromatic index 4 was presented.

关 键 词：外平面图 无圈边色数 最大度 充分条件 

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