最大度为6且不含5-圈和相邻4-圈的平面图是7-全可染的.pdfVIP

第34卷第3期 浙江师范大学学报(自然科学版) v01．34。No．3 2011年8月 JournalofZhejiangNormalUniversity(Nat．Sci．) Aug．2011 文章编号：1001-5051(2011)03-0272-05 最大度为6且不含5．圈和相邻4．圈的平面图 是 7．全可染的 张静雯 (浙江师范大学数理与信息工程学院，浙江金华 321004) 摘 要：运用Discharging方法，证明了最大度为6且不含5-圈和相邻4-圈的简单平面图是7全·可染的．所得 结果改进了现有文献的相关结果． 关键词 ：平面图；全染色；最大度 ；5·圈；相邻4-圈 中图分类号 ：0157．5 文献标识码 ：A Onthe7-total-colorabilityofplanegraphs withmaximum degree6without5-cyclesandadjacent4-cycles ZHANGJingwen (CollegeofMathematics，PhysicsandInformationEngineering。ZhejiangNormalUniversity。J~nhna Zhejiang 321004。China) Abstract：ByusingthedischargingmethodIitwasprovedthatplanegraphswithmaximum dergee6andwith— out5-cyclesandadjacent4-cycleswere7-totally—colorable．Thisimprovedtheknownresultsinliteratures． Keywords：planergaph；totalcoloring；mxaimumdergee；5-cycles；adjacent4-cycles 0 引 言 本文所研究的图是有限简单无向图，文中未加定义的术语和记号参阅文献[1]． 如果图G可嵌入到平面上，使得边仅在端点处相交，则称图G是可平面图；可平面图在平面内的一 个嵌入叫平面图．对于平面图G，分别用 ，E，F，△和 表示平面图G的顶点集、边集、面集、最大度和最 小度．．圈是指长度为k的圈；两个圈相邻是指该两个圈至少有l条公共边． 设平面图G=(，E)，若映射 ：uE {l，2，…，k}，使得对任意相邻或相关联的元素 ，Y∈VLJE 都有 ()≠咖(Y)，则称G是后一全可染的．显然，给每一个图进行全染色至少要用△+1种颜色．文献 [23]猜想 ：任何简单图G都是 (△+2)．全可染的．这一猜想就是著名的全染色猜想 (TotalColoringCon． jecture)，简记为TCC． 即使对于平面图，TCC也未得到完整的证明．唯一未解决的困难情形是△=6．这方面的一些研究结 果可参见文献 [4．8]．人们期望得到关于简单平面图全染色的最好结果，即证明平面图是 (△+1)·全可 染的．到 目前为止，已经证明了在大多数情况下，简单平面图是 (△+1)一全可染的．文献 [9一l1]分别证明 了△≥l1，△=10和A=9的平面图是(△+1)一全可染的；文献[12]证明了△≥7且不含4一圈的简单平面 收文 日期：2010-01-02；修订 日期：2010-09—13 基金项 目：浙江省自然科学基金资助项 目(Y6090699) 作者简介：张静雯(1986一)，女，陕西西安人，硕士研究生．研究方向：运筹学与控制论；图论 第3期 张静雯：最大度为6且不含5．圈和相邻4-11t~平面图是7．全可染的 273 图是 (△+1)一全可染的．本文研究的是关于 △=6的平面图的全染色问题，得到如下结果： 定理 1 设 G是△：6且不含5．圈和相邻4一圈的平面图，则图G是7一全可染的． 1 定理 1的证明 假设定理 1不成立，并设图G是定理 1的一个使 (G)=II+lEl最小的反例，即△(G)=6且不 含5一圈和相邻