最大度为7且不含带弦5-圈的平面图是8-全可染的  

Plane graphs with maximum degree 7 and without 5-cycles with chords are 8-totally-colorable

作　　者：王应前[1] 孙强[1] 陶鑫[1] 沈岚[1] 

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

出　　处：《中国科学：数学》2011年第1期95-104,共10页Scientia Sinica：Mathematica

基　　金：浙江省自然科学基金(批准号:Y6090699);国家自然科学基金(批准号:10971198);浙江省创新团队(批准号:T200905)资助项目

摘　　要：若能用k种颜色给图的顶点和边同时进行染色使得相邻或相关联的元素(顶点或边)染不同的色,则称这个图是k-全可染的.显然,给最大度为△的图进行全染色,至少要用△+1种不同的色.本文证明最大度为7且不含带弦5-圈的平面图是8-全可染的.这一结果进一步拓广了(△+1)-全可染图类.Let G = （V, E） be a graph with the set of vertices V and the set of edges E. If one can use k colors to color the elements in V ∪ E such that any pair of adjacent or incident elements receive distinct colors, then G is said to be k-totally-colorable. Clearly, at least △＋ 1 colors are needed to color a graph totally, where A is the maximum degree of G. It is known that the plane graphs with maximum degree △ ≥ 8 and without 5-cycles with chords are （△ ＋ 1）-totally-colorable. In this paper, we prove that the plane graphs with maximum degree 7 and without 5-cycles with chords are 8-totally-colorable.

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

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