关于最大度为7的平面图全染色的一个注记  

A note on total coloring of plane graphs with maximum degree seven

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

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

出　　处：《浙江师范大学学报（自然科学版）》2011年第1期14-21,共8页Journal of Zhejiang Normal University:Natural Sciences

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

摘　　要：给最大度为Δ的图进行全染色至少要用Δ+1种颜色.全染色猜想断言每个图都是(Δ+2)-全可染的.但即使对于平面图,全染色猜想依然未得到证实.在该研究方向已证明满足下述条件之一的最大度为Δ的平面图是(Δ+1)-全可染的:1)Δ≥9;2)Δ=8且不含相邻三角形.证明了最大度为7且不含带弦4-圈和带弦5-圈的平面图是8-全可染的.该结果进一步拓展了(Δ+1)-全可染平面图类.To color a graph with maximum degree Δ totally,at least Δ＋1 colors are needed.The total coloring conjecture asserts that every graph is（Δ＋2）-totally-colorable.Even for plane graphs,this conjecture remains open.It had been proved so far that plane graphs with maximum degree Δ could be（Δ＋1）-totally-colorable if they satisfied one of the following conditions： 1） Δ≥9;2） Δ=8 and had no adjacent triangles.It was proved that a plane graph with maximum degree 7 could be 8-totally-colorable if it had neither chordal 4-cycle nor chordal 5-cycle.This result extended the known class of（Δ＋1）-totally-colorable plane graphs.

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

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