不含带弦7-圈的平面图的全染色  

Total Coloring of Planar Graph without 7-cycles with Chords

作　　者：蔡建生[1] 

机构地区：[1]潍坊学院数学与信息科学学院,潍坊261061

出　　处：《应用数学学报》2014年第2期286-296,共11页Acta Mathematicae Applicatae Sinica

基　　金：山东省自然科学基金(ZR2013AM001)资助项目

摘　　要：设G=(V,E)是一个以V为顶点集,E为边集的图.图G的一个k-全染色是一个映射φ:VuE→{1,2,…,k}使得φ(x)≠φ(y)对所有相邻和相关联的元素x和y都成立.若G有一个k-全染色,则G称为k-全可染的.本文应用权转移方法证明了最大度为7的不含带弦7-圈的简单平面图是8-全可染的.这个结果改进了同类型的相关结果.Let G = （V, E） be a graph with sets of vertices and edges V and E, respectively. A total k-coloring of G is a mappingφ：V∪E→{1,2…,k}such that φ（x） φ（y） whenever x and y are two adjacent or incident elements of V ∪E. G is totally k-colorable if it admits a total k-coloring. In this paper, we use discharging method to prove that plane graphs with maximmn degree 7 and without chordal 7-cycle are totally 8-colorable. This improves some known results on this topic of totally 8-colorability of plane graphs with maximum degree 7.

关 键 词：简单图 平面图 全染色 最大度 带弦7-圈 

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