平面图的无圈边染色  

Acyclic edge coloring of planar graphs

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

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

出　　处：《江苏师范大学学报（自然科学版）》2014年第3期22-26,共5页Journal of Jiangsu Normal University：Natural Science Edition

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

摘　　要：一个图G的无圈边染色是一个正常的边染色,使得不产生双色圈.Fiamˇcik和Alon等分别提出了著名的无圈边色数猜想:每一个简单图G是无圈边(Δ+2)可染的,其中Δ是G的最大度.证明了对于不含3圈和5圈相邻的平面图猜想成立.An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are pro-duced.The acyclic chromatic index a′(G)of G is the smallest k such that G has an acyclic edge coloring using k col-ors.Fiamˇcik and Alon et al,independently,made a conjecture that every simple graph G has a′(G)≤Δ+2,whereΔdenotes the maximum degree of G.In this paper,this conjecture for planar graphs G without a 3-cycle adjacent to a 5-cycle are confirmed.

关 键 词：无圈边色数 平面图 最大度 圈 

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