最大度是4的可平面图的边染色  

Edge Coloring Of Planar Graphs With Δ=4

作　　者：倪伟平[1] 

机构地区：[1]枣庄学院数学与信息科学系,山东枣庄277160

出　　处：《枣庄学院学报》2010年第5期49-54,共6页Journal of Zaozhuang University

摘　　要：对于最大度是Δ的可平面图G,如果χ′(G)=Δ称G为第一类图,如果χ′(G)=Δ+1称G为第二类图,χ′(G)表示G的边染色数.1965年,Vizing举例说明,最大度是4的平面图中不仅有第一类图,也有第二类图.论文运用Discharge方法及临界图的重要性质证明:最大度是4,不含5圈和6圈,且任意两个相交面的度不相同的可平面图是第一类图.LetGbe a planar graph of maximum degreeΔ,Gis of class1 ifχ′（G）=Δand of class2 ifχ′（G）=Δ＋1,whereχ′（G） denotes the chromatic index ofG.In 1965,Vizing proved both class 1 and class 2 planar graph exist in planar graphs with Δ=4.By applying a discharging method,we show that a planar graphGwith maximum degree4 is of class 1,ifGdoes not contain 5-cycles and 6-cycles,and contains no intersecting faces with same degrees.

关 键 词：平面图 边染色 最大度 第一类图 

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