最大度为8且无4-扇的平面图的9-全可染性  

On the Total 9-colorability of Plane Graphs with Maximum Degree 8 without 4-fans

作　　者：李慧慧[1] 王应前[1] 

机构地区：[1]浙江师范大学数理与信息工程学院,金华321004

出　　处：《应用数学学报》2013年第6期988-999,共12页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金资助项目(11271335)

摘　　要：设G=(VE)是一个以V为顶点集,E为边集的图.图G的一个κ-全染色是一个映射φ:VUE→{1,2,…,k}使得φ(x)≠φ(y)对所有相邻或相关联的元素x和y都成立.若G有一个k-全染色,则说G是k-全可染的.令△为G的最大度.显然,对G进行全染色,至少需要△+1个颜色.Behzad和Vizing相互独立地猜想每个(简单)图都是(△+2)-全可染的.已知最大度△≥9的平面图是(△+1)-全可染的.通过研究极小反例的新的可约性质,本文运用权转移方法证明了最大度为8且不含4-扇的平面图是9-全可染的,这里的4-扇是指交于一点的4个相继的3-面.这一结果改进了若干同类型的相关结果.t 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 Φ：VuE→{1…2,k）such that Φ（x）≠Φ（y） whenever x and y are two adjacent or incident elements of V U E. G is totally k-colorable if it admits a total k-coloring. Let A denote the maximum degree of G. Clearly, at least A ＋ 1 colors are needed to totally color G. Behzad and Vizing independently conjectured that every graph is totally （A ＋ 2）-colorable. It is known that plane graphs with maximum degree A ~ 9 are totally （A ＋ 1）-colorable. By exploring new reducibility of minimal counterexample, we use discharging method to prove that plane graphs with maximum degree 8 and without 4-fans are totally 9-colorable, where a k-fan in a plane graph consists of k consecutive 3-faces intersecting at a vertex. This improves some known results on the topic of total 9-colorability of plane graphs with maximum degree 8.

关 键 词：平面图 全染色 最大度 扇 

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