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

Advances in Education教育进展, 2023, 13(10), 7943-7946Published Online October 2023 in Hans. https:///journal/aehttps:///10.12677/ae.2023.13101233关于图论课程教学中对染色问题的研究初亚男，赵操苏州科技大学数学科学学院，江苏苏州收稿日期：2023年9月18日；录用日期：2023年10月17日；发布日期：2023年10月24日摘要图论起源于著名的哥尼斯堡七桥问题，是离散数学的重要分支。

它在计算科学、社会科学和自然科学等多个领域都有广泛应用。

本文主要研究广义Petersen图的非正常点染色问题，构造满足条件的染色方式。

旨在帮助学生更好地理解图论基本概念，掌握图论中的基本技巧方法，从而培养学生科学解决问题的能力。

关键词非正常染色，广义Petersen图，邻点Research on Coloring Problem of GraphTheory in Curriculum TeachingYanan Chu, Cao ZhaoSchool of Mathematical Sciences, Suzhou University of Science and Technology, Suzhou JiangsuReceived: Sep. 18th, 2023; accepted: Oct. 17th, 2023; published: Oct. 24th, 2023AbstractGraph theory, which originated from the famous Seven Bridges problem, is an important branch of discrete mathematics. It has extensive applications in many fields such as computing science, so-cial science and natural science. In this paper, we mainly study improper coloring of generalized Petersen graphs and construct a coloring with certain requirement. It aims to help students un-derstand the basic concepts and skills in graph theory, so as to guide student to develop the ability of solving scientific problems.KeywordsImproper Coloring, Generalized Petersen Graph, Neighbors初亚男，赵操Copyright © 2023 by author(s) and Hans Publishers Inc. This work is licensed under the Creative Commons Attribution International License (CC BY 4.0)./licenses/by/4.0/1. 引言随着计算机科学的飞速发展，图论作为离散数学的一个重要分支，越来越成为各个领域研究的热点。

最大度为6的平面图的全染色的开题报告题目：最大度为6的平面图的全染色一、研究背景与意义全染色问题指给定一个图，在每个点上涂一个颜色，要求相邻的两个点颜色不同。

本问题考虑最大度为6的平面图的全染色问题。

其中，平面图指的是可以嵌入在平面上且边不相交的图。

此问题的研究有多个应用场景。

例如，在制作地图时，需要标识每个地区的颜色，而且相邻地区颜色应不同。

全染色问题也与计算机网络中的路由算法有关。

此外，全染色问题也是图论领域中具有挑战性的问题之一，其解决方法对图论的研究有重要意义。

二、研究目的与内容本研究的目的是研究最大度为6的平面图的全染色问题，探求其解决方法和关键技术。

本研究的内容分为以下几个方面：1. 研究最大度为6的平面图的基本性质和特征，分析其对全染色问题的影响。

2. 探索构造最大度为6的平面图的方法，通过改变图的结构和边的连接方式来达到全染色的目的。

3. 根据图的特征和结构，设计并实现相应的算法来解决全染色问题。

其中，有多种经典算法可以进行参考和借鉴。

4. 对于算法的效率和正确性进行分析和评估。

通过实验和数据分析来测试算法的性能和适用性。

三、研究方法与步骤本研究主要采用以下几种研究方法：1. 文献调研：通过查阅文献，了解该领域的研究现状和发展趋势。

同时，也可以了解到相关算法的优缺点和局限性。

2. 理论分析：对于最大度为6的平面图特征和结构进行分析和研究，通过推导和证明等数学方法，得出一些结论和结构特性。

3. 算法设计：利用上述分析结果，设计合适的算法来解决全染色问题。

其中，可以采用贪心算法、回溯算法、分支界定算法等来求解。

4. 实验验证：将算法应用到实际案例中，测试其效率和正确性。

通过对比实验结果，评估算法的性能和适用性。

具体的研究步骤如下：1. 阅读平面图的相关背景知识和全染色问题的基本概念。

2. 对最大度为6的平面图进行分类和分析，得出其特征和结构特性。

3. 探索构造最大度为6的平面图的方法，结合其特性来达到全染色的目的。

最大度是5的可平面图的边染色倪伟平【摘要】对于最大度是Δ的可平面图G,如果χ′(G)=Δ,称G为第一类图;如果χ′(G)=Δ+1,称G为第二类图.χ′(G)表示G的边染色数.1965年,Vizing举例说明Δ=5的可平面图中既有第一类图,也有第二类图.作者运用Discharge方法证明最大度是5且不包含有弦的4-圈和有弦的5-圈,或不包含有弦的4-圈和有弦的6-圈的可平面图是第一类图.【期刊名称】《安徽大学学报（自然科学版）》【年(卷),期】2010(034)003【总页数】6页(P18-23)【关键词】平面图;边染色;最大度;圈【作者】倪伟平【作者单位】枣庄学院,数学与信息科学系,山东,枣庄,277160【正文语种】中文【中图分类】O157.5文中考虑的图都是简单、无向有限图.若图G可以表示在平面上,并且任意两条边仅在其端点处才可能相交，则称G是可平面图，图G的这种平面上的表示法称为G 的一个平面嵌入，或称为平面图．分别用V(G)、 E(G)、F(G)、Δ(G)(简记为Δ)表示G的顶点集合、边集合、面集合、最大度．用d(x)表示x在G中的度数，x∈V(G)∪F(G)．用dk(v)表示点v的度数为k的邻点的个数，dk+(v)表示点v的度数不小于k的邻点的个数．度数为k的点(或面)称为k-点(或k-面)，度数不小于k的点(或面)称为k+-点(或k+-面)．若一个3-面f关联3个度数分别为i,j,k的顶点，其中，i≤j≤k,则称f为(i,j,k)-面．设C是G中长度为k的圈，如果xy∈E(G)\E(C)，其中，x,y∈V(C)，称xy为C的一条弦，C为有弦的k-圈．若存在一个映射φ:E(G)→{1,2,…，k}，对G中任意两条相邻接的边e1和e2,有φ(e1)≠φ(e2)，则称G是k-边可染色的，使得图G具有k-边可染色的最小的正整数k定义为G的边色数，记作χ′(G)．若图G满足χ′(G)=Δ(G)，称G为第一类图，若χ′(G)=Δ(G)+1，称G为第二类图．若图G是连通的第二类图,并且去掉任意边e∈G后,G-e是第一类图,则称G是一个临界图．最大度为Δ的临界图简称Δ-临界图．显然,每个Δ-临界图(Δ≥2)是2-连通的．文献[2]证明了每个Δ≥8的简单平面图是第一类图，同时猜想这个结论对Δ≥6的简单平面图也是成立的，给出了Δ∈{2,3,…,5}的简单平面图存在第二类的例子．文献[3]、[4]独立证明了Δ=7时文献猜想成立．文献[5]、[6]给出了Δ=6的可平面图是第一类图的充分条件．对于Δ=5的可平面图，文献[7]证明了Δ=5且围长不小于4的可平面图是第一类图；文献[9]给出了Δ=5且不含4-圈或不含5-圈的可平面图是第一类图；文献[10]证明了Δ=5且没有相交三角形的简单平面图是第一类图．下面将运用Discharge方法及临界图的重要性质证明：最大度是5且不包含有弦的4-圈和有弦的5-圈，或不包含有弦的4-圈和有弦的6-圈的可平面图是第一类图．1 临界图的性质引理1 设G是一个Δ-临界图，u,v∈V(G)且u,v相邻接，d(v)=k，那么(1) 若k<Δ，则u至少邻接于Δ-k+1个度为Δ的顶点；(2) 若k=Δ，则u至少邻接于两个度为Δ的顶点；(3) d(v)+d(u)≥Δ+2．引理2 设G是一个Δ-临界图,xy∈E(G),使得d(x)+d(y)=Δ+2,那么(1) 每个v∈N({x,y})/{x,y}是Δ-点;(2) 每个v∈N(N({x,y}))/{x,y}满足d(v)≥Δ-1；(3) 如果d(x)<Δ,d(y)<Δ,则每个v∈N(N({x,y}))/{x,y}是Δ-点.引理3 如果图G存在3个不同的顶点x,y,z满足下列两个条件：(1) xy∈E(G),xz∈E(G),d(z)<2Δ-d(x)-d(y)+2；(2) xz包含在至少d(x)+d(y)-Δ-2个不包含顶点y的三角形中．则G不是Δ-临界图.2 主要结论及证明引理4 设G是5-临界图，s是v∈V(G)所关联的3-面的个数．若G不含有弦的4-圈和有弦的5-圈，则(1) G中每个3-点v至多关联1个3-面．s=1时，v还关联2个5+-面．(2) G中每个4-点v至多关联2个3-面．s≥1时，v还关联2个5+-面．(3) G中每个5-点v至多关联2个3-面．若v不与2-点邻接，当s=2时，v还关联3个5+-面；当s=1时，v还关联2个5+-面．若v与2-点邻接，当s=2时，如果v关联(2,5,5)-面及(5,5,5)-面，则v 还关联2个5+-面和1个6+-面；如果v关联2个(5,5,5)-面，则v还关联3个5+-面．当s=1时，如果v关联(2,5,5)-面，则v至少关联1个5+-面和1个6+-面；如果v关联(5,5,5)-面，则v至少还关联2个5+-面．引理5 设G是5-临界图，s是v∈V(G)所关联的3-面的个数．若G不含有弦的4-圈和有弦的6-圈，则(1) G中每个3-点v至多关联1个3-面．s=1时，v至少关联1个6+-面．(2) G中每个4-点v至多关联2个3-面．s=2时，v关联2个6+-面；s=1时，v至少关联1个5+-面．(3) G中每个5-点v至多关联2个3-面．若v不与2-点邻接，当s=2时，则v至少关联2个6+-面；当s=1时，则v至少关联2个5+-面．若v与2-点邻接，当s=2时，v关联2个6+-面．当s=1时，若v关联(2,5,5)-面，则2-点关联的另一面f为5-面或为7+-面.如果f为5-面，则v还关联1个5+-面和1个6+-面.如果f为7+-面，则v至少还关联1个5+-面.若v关联(5,5,5)-面，则v至少还关联1个5+-面．定理1 设G是最大度为5的可平面图．若G中不含有弦的4-圈和有弦的5-圈,或不含有弦的4-圈和有弦的6-圈，则G是第一类图．证明假设定理1不成立,即G是第二类图．不失一般性,可以假设G是5-临界图，那么G是2-连通的．因此，G的每个面的边界是一个圈,且每条边位于2个不同面的边界上．将Euler公式变形可得对任意x∈V(G)∪F(G),定义初值ch(x)为ch(x)=d(x)-4.根据给出的交换规则(Discharging rules)，对每一个x∈V(G)∪F(G)的ch(x)进行调整，从而得到新的值ch′(x)．因为所作的调整始终保证不影响其和式的值，所以有如果可以证明对于每一个x∈V(G)∪F(G)，都有ch′(x)≥0，则与上式矛盾，从而定理得证．情况1 若G中不含有弦的4-圈和有弦的5-圈．定义规则如下:R1对每个5-点v，v分值如下：(1) v分值1给其邻接的2-点，分值给其邻接的每个3-点，分值给其邻接的每个4-点；(2) 若v邻接5-点u，u与2-点x邻接，而v与x不邻接，则v分值给u．R2对每个3-点v，v分值给其关联的每个3-面．R3对每个4-点v，v分值给其关联的每个3-面．R4对每个度为3的面f，设x、y、z是f的3个不同顶点，且d(x)≤d(y)≤d(z)．(1) 若f是(2,5,5)-面，则y、z分别分值给f；(2) 若f是(3,4,5)-面，则x分值分值分值给f；(3) 若f是(3,5,5)-面，则x分值分值分值给f；(4) 若f的顶点的度至少为4，则x、y、z分别分值给f．R5设f是度至少为5的面，则f分值给与其关联的每个顶点．假设f∈F(G)，则d(f)≥3.如果d(f)=4，则ch(f)=0，取ch′(f)=0．如果d(f)≥5，则ch(f)=d(f)-4≥1．由R5，有ch′(f)=如果d(f)=3，则ch(f)=-1．由于Δ=5，由引理1～3知，f必为下列3-面之一：(2+,5,5)-面，(3,4,5)-面，(4,4,4)-面，(4,4,5)-面，(5,5,5)-面，由R4，有ch′(f)=-1+1=0.对于每个v∈V(G),有d(v)≥2.(1) 设d(v)=2,则ch(v)=-2.由引理1,v与2个5-点邻接.由R1(1),有ch′(v)=ch′(v)=-2+1×2=0.(2) 设d(v)=3,则ch(v)=-1.由引理1,v至少邻接2个5-点，由R1(1)，v至少得若s=1，由引理4(1)及R5，v至少得值再由R2，有若s=0，有(3) 设d(v)=4，则ch(v)=0．由引理1，v至少邻接两个5-点，由R1(1)，v至少得值由引理4(2)，有s≤2．若s≥1，由引理4(2)及R5，v至少得值由R3，v至多分值给其关联的3-面，所以，若s=0，则有(4) 设d(v)=5，则ch(v)=1．由引理1,min {d(u)|u∈N(v)}≥2且至多有一个2-点，至少有2个5-点与v邻接．由引理4(3)，有s≤2．当d2(v)=1时，由引理2，有d5(v)=4．如果s=2且v关联(2,5,5)-面和(5,5,5)-面，由引理4(3)及R5，v至少得值由R1(2)，v得值由R1(1)、R4(1)、R4(4)，v至多分出值所以，如果s=2且v关联2个(5,5,5)-面，由引理4(3)及R5，v至少得值由R1(2)，v至少得值由R1(1)及R4(4)知，v至多分值所以，有如果s=1且v 关联(2,5,5)-面，由引理4(3)及R5，v至少得值由R1(1)、R4(1)，有如果s=1且v 关联(5,5,5)-面，由引理4(3)及R5知，v至少得值再根据R1(1)、R4(4)，有如果s=0，则有ch′(v)=1-1=0．当min{d(u)|u∈N(v)}=3时，由引理1,v至多与2个3-点、至少与3个5-点邻接．假如d3(v)=2，由引理3，v至多关联1个3-面，为(5,5,5)-面．当s=1时，由引理4(3)及R5，v至少得值再由R1(1)、R4(4)，有当s=0时，由R1(1)，有假如d3(v)=1且d4(v)=1，由R1(1)，v分值给其邻接的3-点和4-点，由R4(2)、R4(3)、R4(4)，v至多分值给其关联的2个3-面．由引理4(3)及R5，当s=2时，v至少得值时，v至少得值所以，s=2时，有时，有时，有假如d3(v)=1且d5(v)=4，由R1(1)、R4(3)、R4(4)，v至多分值当s≥1时，由引理4(3)及R5，v 至少得值所以，有当s=0时，则有当min{d(u)|u∈N(v)}≥4时，由引理1,有d5(v)≥2，d4(v)≤3．由R1(1)，v至多分值给其邻接的4-点，由R1(2)，v至多分值给其邻接的5-点，由R4(4)，v至多分值给与其关联的3-面．当s≥1时，由引理4(3)及R5，v至少得值所以，当s=0时，有情况1得证．情况2 若G中不含有弦的4-圈和有弦的6-圈．定义规则如下:R1对每个5-点v，v分值如下：(1) v分值1给其邻接的2-点，分值给其邻接的每个3-点，分值给其邻接的每个4-点；(2) 若v邻接5-点u，u与2-点x邻接，而v与x不邻接，则v分值给u．R2每个3-点、4-点分值给其关联的每个3-面．R3对每个度为3的面f，设x、y、z是f的3个不同顶点，且d(x)≤d(y)≤d(z)．(1) 若f是(2,5,5)-面，则y、z分别分值给f；(2) 若f的顶点的度至少为3，则x、y、z分别分值给f．R4设f是度至少为5的面，则f分值给与其关联的每个顶点．假设f∈F(G)，则d(f)≥3．如果d(f)=4，则ch(f)=0，取ch′(f)=0．如果d(f)≥5，则ch(f)=d(f)-4≥1，由如果d(f)=3，则ch(f)=-1．由于Δ=5，根据引理1～3，f 必为下列3-面之一：(2+,5,5)-面，(3,4,5)-面，(4,4,4)-面，(4,4,5)-面，(5,5,5)-面．由R3(1)、R3(2)，有ch′(f)=-1+1=0.对每个v∈V(G),有d(v)≥2.(1) 设d(v)=2,则ch(v)=-2.由引理1,v与2个5-点相邻接.由R1(1),有ch′(v)=-2+1×2=0．(2) 设d(v)=3,那么ch(v)=-1.由引理5(1)，s≤1．由引理1,v至少邻接2个5-点，由R1(1)，v至少得值当s=1时，由引理5(1)及R4，v至少得值再由R2，有当s=0时，有(3) 设d(v)=4，则ch(v)=0．由引理5(2)，有s≤2．由引理1，v至多与1个3-点、至少与2个5-点邻接，由R1(1)，v至少得值所以，当s=0时，有当s=1时，由引理5(2)及R4，v至少得值再由R2，有当s=2时，由引理5(2)及R4，v至少得值再由R2，有(4) 设d(v)=5，则ch(v)=1．由引理1,min{d(u)|u∈N(v)}≥2且至多有1个2-点、至少有2个5-点与v邻接．由引理5(3)，有s≤2．当d2(v)=1时，根据引理2，有d5(v)=4．若s=2，则由引理5(3)及R4，v至少得值由R1(2)，v至少得值由R1(1)、R3(1)、R3(2)，v至多分值给其邻接的2-点及其关联的3-面，所以，若s=1，并且v关联(2,5,5)-面，则由引理5(3)及R4，v 至少得值由R1(1)、R3(1)，有若s=1，并且v关联(5,5,5)-面，则由引理5(3)及R4，v至少得值由R1(2)，v得值再由R1(1)、R3(2)，有若s=0，有ch′(v)=1-1=0．当min{d(u)|u∈N(v)}=3时，由引理1,v至多与2个3-点，至少与3个5-点邻接．假如d3(v)=2，由引理3，v至多关联1个3-面，为(5,5,5)-面．s=1时，由引理5(3)及R4，v至少得值由R1(1)、R3(2)，有时，由R1(1)，有假如d3(v)=1，由R1(1)，v至多分值给其邻接的3-点和4-点．当s=2时，由引理5(3)及R4，v至少得值由R3(2)，有时，由引理5(3)及R4，v至少得值再由R3(2)，有时，有当min{d(u)|u∈N(v)}≥4时，由引理1,有d5(v)≥2，d4(v)≤3．若s=2，则由引理5(3)及R4，v至少得值由R1(1)、R1(2)、R3(2)，v至多分值给其邻接的4-点、邻接的5-点及其关联的3-面，所以，若s=1，则由引理5(3)及R4，v至少得值再根据R1(1)、R1(2)、R3(2)，有若s=0，则由R1(1)、R1(2)，有情况2得证．由情况1、2的证明可知，定理1成立.参考文献：[1] Vizing V G. On an estimate of the chromatic index of a p-graph[J].Diskret Analiz，1964,3(1):25-30.[2] Vizing V G. Critical graphs with given chromatic class[J].Diskret Analiz，1965,5(1):9-17.[3] Sanders D P, Zhao Y. Planar graphs of maximum degree seven are class 1[J].J Combin Theory Ser B，2001,83(2):201-212.[4] Zhang L. Every planar with maximum degree 7 is of class 1[J].Graphs Combin,2000,16(4):467-495.[5] Zhou G. A note on graphs of class 1[J].Discrete Math,2003,262(1/3):339-345.[6] Bu Y, Wang W. Some sufficient conditions for a planar graph of maximum degree six to be class 1[J].Discrete Math,2006,306(13):1440-1445.[7] Li X, Luo R. Edge coloring of embedded graphs with largegirth[J].Graphs Combin,2003,19(3):393-401.[8] Lam P, Liu J, Shu W, et al. Some sufficient conditions for a planar graph to be of class1[J].Congr Numer,1999,136(1):201-205.[9] 吴玉文.关于平面图的边剖分的若干结果[D].山东大学数学学院,2007.[10] 陈永珠,王维凡.第一类平面图的一个充分条件[J].浙江师范大学学报:自然科学版,2007,30(4):416-420.。

[Δ]（G）=8且不含4-圈的平面图的完备染色
完备染色是图论中一个重要的概念，它指的是对一个图的顶点进行染色，使得每个顶点都被染成不同的颜色，并且相邻的顶点不能被染成相同的颜色。

而完备染色的图中不能含有4-圈，也就是不能含有长度为4的圈。

在图论中，我们经常研究各种不同性质的图，完备染色也是图论研究的一个重要方面。

在图论中，我们常常研究完备染色的问题。

完备染色的概念来源于实际生活中的染色问题，比如地图染色、时间表染色等。

而不含4-圈的平面图的完备染色问题是一个经典的图论问题，对此问题的研究有助于我们更深入地理解图论的性质和规律。

在研究不含4-圈的平面图的完备染色问题时，我们可以用数学方法进行分析和证明。

通过建立数学模型，我们可以得到一些关于这类图的性质和规律的结论。

这些结论对于图论领域的研究、应用和发展都具有重要意义。

在实际应用中，完备染色的概念也有着广泛的应用。

在地图染色问题中，我们需要对地图中的各个国家进行染色，使得相邻的国家染成不同的颜色。

而在时间表染色问题中，我们需要对课程表或员工排班表进行染色，使得相邻的时间段或员工不会出现冲突。

完备染色的概念在实际生活和工作中都具有一定的应用价值。

关于平面图的7-全可染性的一个注记陶鑫;王应前【摘要】研究了平面图的全染色问题.运用Discharging方法,结合一些排除的构形,得到:最大度为6且不含5-圈和6-圈的简单平面图是7-全可染的.所得结果推广了现有文献的相关结果.%It was studied the total coloring problem of plane graphs. By using method of discharging and combing with the exclusion of some configurations, it was proved that plane graphs with maximum degree 6 without 5-cycles and 6-cycles were 7-totally-colorable. The present results extended the relevance results in literatures.【期刊名称】《浙江师范大学学报（自然科学版）》【年(卷),期】2011(034)003【总页数】5页(P262-266)【关键词】平面图;全染色;最大度;5-圈;6-圈【作者】陶鑫;王应前【作者单位】浙江师范大学数理与信息工程学院,浙江金华 321004;浙江师范大学数理与信息工程学院,浙江金华 321004【正文语种】中文【中图分类】O157.5本文的图指的是有限简单无向图，文中未加定义的术语和记号参阅文献［1］．设G=(V，E)表示顶点集为V、边集为 E的图．若能用k种颜色对G进行染色，使得任意2个相邻或相关联的元素染有不同的色，则称G是k-全可染的．设F，Δ和δ分别表示平面图G的面集、最大度和最小度．显然，给每一个图进行全染色至少要用Δ+1个色．猜想1［1］任何简单图G都是(Δ+2)-全可染的．这一猜想被称为全染色猜想，简记为TCC．即使对于平面图，TCC在目前还没有得到完整证明．剩下未解决的情形是Δ=6［2-8］．有趣的是，对于简单平面图，大多数情况是(Δ+1)-全可染的［9-10］．猜想2［11］若G是4≤Δ≤8的简单平面图，则G是(Δ+1)-全可染的．对此，文献［12］证明了Δ≥7且不含有4-圈的平面图是(Δ+1)-全可染的;文献［11］证明了Δ=7且不含相邻三角形的平面图是8-全可染的．笔者则研究了Δ=6且不含5-圈和6-圈的平面图的全染色问题．定理1 若G是Δ=6且不含5-圈和6-圈的平面图，则G是7-全可染的．证明假设定理1不成立，并设G是定理1的一个使σ(G)=|V|+|E|最小的反例，即G本身不是7-全可染的，但它的每一个真子图都是7-全可染的，则可得断言1．断言1［9］ G是2-连通的，从而δ≥2且G的每个面的边界都是圈．把度为k的点叫做k-点．类似地，度不小于k的点叫做k+-点，度不大于k的点叫做k－-点．断言2［12］设xy∈E．若d(x)≤3，则d(x)+d(y)≥Δ +2=8．特别地，G 中2-点只与6-点相邻，3-点只与5+-点相邻．断言3 G不含图1所示的结构．其中标记为·的点在G中没有其他邻点．图1 G不含有的构形只证第5种情形(如图1(e)所示)，其他情形的证明可参阅文献［10-11，13］．假设G含有如图1(e)所示的构形．根据σ(G)的极小性知，G'=G －uv是7-全可染的．令φ:V(G')∪E(G')→{1，2，…，7}是G'的一个7-全染色．设对于x∈V，S(x)是与顶点x以及与x相关联的边染得的颜色集．如图1(e)所示，设 S(u)={1，2，…，6}，其中φ(uq)=3，φ(uw)=4，φ(vm)=7，因此φ(pq)=7．否则将 3 染给 uv，7 染给uq，这样得到G的一个7-全染色，矛盾．此时交换pq与pw的颜色，将3染给uv，7染给uq，这样得到了G的一个7-全染色，矛盾．因此，断言3成立．以下将运用Discharging方法导出完成定理1证明所需要的矛盾．首先，给G的顶点v分配初始权ch(v)=2d(v)－6，给G的面f分配初始权ch(f)=d(f)－6．由握下面将定义一个权转移规则，重新分配点和面的权，并设ch'(x)是重新分配点和面的权后元素x∈于只是在同一个图的点和面之间进行权转移，权的总和应该保持不变，因此得到－12≥0，即得到了证明定理1所需要的矛盾．权转移规则如下(如图2所示):R1:转向2-点的权与2-点相邻的2个6-点都向此2-点转移权1．R2:转向3-面的权由断言2知，3-面上只有1个3－-点，因此R2．1:若3-面含有3－-点，则此3-面上的2 个5+-点都向此R2．2:若3-面不含3－-点，则此3-面上的3 个4+-点都向此3-面转移权 1．R3:转向4-面的权R3．1:若4-面含有2个3－-点，则此4-面上的2个5+-点都向此4-面转移权1; R3．2:若4-面含有1个3－-点，则此4-面上与此3－-点相对的那个4+-点向此R3．3:若4-面不含3－-点，则此4-面上的4 个4+-点都向此4-面图2 权转移规则首先考察面的新权．设 f为3-面．若 f有1 个3 －-点，则根据R2．2，ch'(f)=ch(f)+1 ×3=0．设 f为4-面．若 f含有2 个3－-点，则根据 R3．1，ch'(f)=ch(f)+1 ×2=0;若f 含1 个3－-点，则根据由G不含5-圈和6-圈知G不含5-面和6-面，故无需验证5-面和6-面的新权．设f为7+-面．由权转移规则知f既不转出权也不接受权，因此ch'(f)=ch(f)=d(f)－6＞0．综上所述，对任意的面f∈F，ch'(f)≥0．其次考察顶点的新权．设v为2-点．由断言2和R1知，ch'(v)=ch(v)+1×2= －2+2=0．设v为3-点．由权转移规则知v既不转出权也不接受权，故ch'(v)=ch(v)=0．下面用t表示与v关联的3-面个数．设 v为4-点．由 G 不含5-圈和6-圈知t≤2，且 v至少与2 个7+-面关联．根据R2．2 和 R2．3，v至多转移权1给每个相关联的3-面，至多转移设v为5-点．由G不含5-圈和6-圈知t≤3，且v至少与2个7+-面关联．又由断言3(如图1(a)所示)知v至多与2个含有3－-点的3-面关联，根据R2和R3 设v为6-点．用n表示与v相邻的2-点个数，显然，n≤6．与6-点相邻的2-点分布情况如图3所示．下面根据n的大小来讨论v的新权:图3 与6-点相邻的2-点分布情况(2≤n≤4)n=6．由断言3(如图1(d)所示)知，v不与3-面关联．由G不含5-圈和6-圈以及断言3(如图1(e)所示)知，与v关联且关联2个与v相邻的2-点的面是7+-面．因此，v关联6个7+-面，根据R1，n=5．由断言3(如图1(d)所示)知t=0．由G不含5-圈和6-圈知，v至少关联5个7+-面，根据R1和R3，n=4．如图3(a1)、图 3(a2)、图 3(a3)所示，由断言3(如图1(d)所示)知t≤1．若t=1，则由 G 不则v至少关联 4个7+-面，根据R1和R3，ch'(v)≥ch(v)－1×4－1×2－0×4=0．n=3．如图3(b1)、图3(b2)、图3(b3)所示，由断言3(如图1(d)所示)知t≤2．若1≤t≤2，则由G不含5-圈和6-圈知v至少关联4个7+-面，根据R1，R2和R3，若 t=0，则 v至少关联3个7+-面，根据 R1和 R3，ch'(v)≥ch(v)－1×3－0×3－1×3=0．n=2．如图3(c1)、图3(c2)、图3(c3)所示，由断言 3(如图1(d)所示)知t≤2．若1≤t≤2，则由 G不含5-圈和6-圈知v至少关联3个7+-面，根据R1，R2．1和R3，若t=0，则v至少关联2个7+-面，根据R1和R3，ch'(v)≥ch(v)－1×2－0×2－1×4=0．设含有2-点的3-面是特殊3-面，记作s-面．由断言3(如图1(b)和图1(c)所示)知，若6-点与一个s-面关联，则6-点不与其他含有3－-点的3-面关联．n=1．若v与s-面关联，则由 G不含5-圈和6-圈知t≤4，且 v至少关联2个7+-面，根据 R1，R2和若v不与s-面关联，则t≤3．若t=3，则根据G不含5-圈和6-圈，v要关联3个7+-面，从而若0≤t≤2，则v至少关联2个7+-面，从而n=0．由G不含5-圈和6-圈知t≤4，且v至少关联2个7+-面，根据R1，R2和R3，至此，对任意的x∈V∪F，ch'(x)≥0已得到验证．定理1得证．参考文献:［1］Bondy J A，Murty U S R．Graph theory［M］．Berlin:Springer，2008．［2］Rosenfeld M．On the total coloring of certain graphs［J］．Israel J Math，1971，9(3):396-402．［3］Kostochka A V．The total coloring of a multigraph with maximal degree 4［J］．Discrete Math，1977，17(2):161-163．［4］Kostochka A V．The total chromatic number of any multigraph with maximal degree five is at most seven［J］．Discrete Math，1996，162(2):199-214．［5］Borodin O V．On the total coloring of planar graphs［J］．J Reine Angew Math，1989，394(2):180-185．［6］陈明，王应前．关于平面图全染色的一个注记［J］．浙江师范大学学报:自然科学版，2007，30(4):421-423．［7］Sanders D P，Zhao Yue．On total 9-coloring planar graphs of maximum degree seven［J］．J Graph Theory，1999，319(1):67-73．［8］Wang Yingqian，Shangguan Minle，Li Qiao．On total chromatic number of planar graphs without 4-cycles［J］．Sci China Ser A，2007，50(1):81-86．［9］Borodin O V，Kostochka A V，Woodall D R．Total coloring of planar graphs with large maximum degree［J］．J Graph Theory，1997，26(1):53-59．［10］Wang Weifan．Total chromatic number of planar graphs with maximum degree ten［J］．J Graph Theory，2007，54(1):91-102．［11］Du Dingzhu，Shen Lan，Wang Yingqian．Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable ［J］．Discrete Appl Math，2009，157(1):2778-2784．［12］Hou Jianfeng，Liu Guizhen，Cai Jiansheng．List edge and list total coloring of planar graphs without 4-cycles［J］．Theoret Comput Sci，2006，369(4):250-255．［13］Kowalik L，Sereni J S，Skrekovski R．Total coloring of plane graphs with maximum degree nine［J］．SIAM J Discrete Math，2008，22(4):1462-1479．。

围长至少为5的平面图的injective染色卜月华;叶飘飘【摘要】通过构造一个(△+3)-临界图G,运用权转移的方法证明了该图G不存在.同时,用反证法证明了:对于围长至少为5的平面图G,若△(G)≥30,则xi(G)≤△+3.这个结论改进了现有的一个结果.%Let G be a plane graph with g(G) ≥5 and xi(G) be the injective chromatic number of G.It was improved some known results by proving thatxi (G) ≤△ + 3 when △ (G) ≥30.The result was obtained by contradiction:Let G be a (△ + 3)-critical graph,a discharging procedure was applied to the proof by showing that G could not exist.【期刊名称】《浙江师范大学学报（自然科学版）》【年(卷),期】2017(040)001【总页数】8页(P1-8)【关键词】平面图;围长;injective染色;面【作者】卜月华;叶飘飘【作者单位】浙江师范大学数理与信息工程学院,浙江金华321004;浙江师范大学行知学院,浙江金华321004;浙江师范大学数理与信息工程学院,浙江金华321004【正文语种】中文【中图分类】O157.5本文仅考虑有限简单图.对于一个平面图G,把它的顶点集、边集、面集、最大度、最小度、围长及图G中u,v间的距离分别记作V(G),E(G),F(G),Δ(G),δ(G),g(G)和dG(u,v).对于图G的一个顶点v,若d(v)=k(或d(v)≥k,或d(v)≤k),则称v为一个k-点(或 k+-点,或k--点).对平面图的面也可以类似定义.∀f∈F(G),记 B(f)为面 f的边界迹.若u1u2…un在B(f)上按顺时针排列,则面 f记为f=[u1u2…un].围长g(G)表示图G中最短圈的长度.图G的正常顶点染色是指对图G的每个顶点分配一种颜色,使得相邻的2个顶点染不同色,其所需的最少颜色数称为图G的色数,记为χ(G).图G的injective k-染色是指映射c:V(G)→{1,2,…,k},使得有公共邻点的2个顶点u,v满足c(u)≠c(v).若图G 有一个injective k-染色,则称图G是injective k-可染的,并称χi(G)=min{k | G是injective k-可染的}为图G的injective色数.Injective染色是由Hahn等[1]提出,并且证明了对任意的平面图G都有Δ(G)≤χi(G)≤(Δ(G))2-Δ(G)+1.随后,人们对平面图的injective染色问题展开了一系列的研究.Doyon等 [2]证明了:对任意围长为g(G)且最大度为Δ的平面图G,有:若g(G)≥7,则χi(G)≤Δ+3;若g(G)≥6,则χi(G)≤Δ+4;若g(G)≥5,则χi(G)≤Δ+8.文献[2-5]研究了稀疏图和平面图的injective色数的上界问题.文献[6]证明了:对于围长g(G)≥6的平面图G,χi(G)≤Δ+3;若Δ≥9,则χi(G)≤Δ+2;若Δ≥17,则χi(G)≤Δ+1.文献[7]证明了:对于围长为g(G)≥5的平面图G,χi(G)≤Δ+6;若Δ≥35,则χi(G)≤Δ+3.问题1 是否存在一个整数M,使得g(G)≥5且Δ≥M的平面图G是injective(Δ+1)-可染的？本文研究围长为g(G)≥5的平面图G的injective染色,证明了下面这个定理:定理1 若图G是g(G)≥5,Δ(G)≥30的平面图,则χi(G)≤Δ(G)+3.若图G不是injective k-可染,但是它的任意真子图都是injective k-可染,则称这样的图G为k-临界图.接下来将研究k-临界图的一些性质.设ni(v)表示与v相邻i-点的个数.若v是图G中的k-点,则记N(v)且{v}).设图G是(Δ+t)-临界图(t≥1),若v是图G中的2-点且D(v)≤Δ+t+1,则称v为轻2-点.否则,称v为重2-点.和分别表示与顶点v相邻的轻2-点个数和与顶点v相邻的重2-点个数.对于顶点v和任意的整数k,d,若k-点v相邻d个2-点,则称v是k(d)-点.称仅与9--点相邻的3(0)-点为轻3(0)-点.设c是图G的injective染色,顶点v所染的颜色记作c(v),对G的一个顶点子集S,所染的颜色集记作c(S)={c(v) | v∈S}.以下是k-临界图G(k≥Δ+1)的一些性质,其证明可见文献[6].性质1 设图G是k-临界图,其中k≥Δ+1,uv∈E(G).若D(u)≤k-1+d(u),则D(v)≥k+d(v).性质2 设图G是(Δ+t)-临界图,其中t≥1,则G不包含相邻2-点且δ(G)≥2.性质3 设图G是(Δ+t)-临界图,其中t≥1,v是2-点,记N(v)={v1,v2}.若D(v)≤Δ+t+1,则∀i∈{1,2},D(vi)≥Δ+t+d(vi).性质4 设图G是(Δ+t)-临界图,其中t≥1,v是3-点,记N(v)={v1,v2,v3}.若D(v)≤Δ+t+2,则∀i∈{1,2,3},D(vi)≥Δ+t+d(vi).由性质4可知,轻3(0)-点与轻3(0)-点不相邻.下面用反证法证明定理1.若定理1的结论不成立,则存在平面图G′,使g(G′)≥5,Δ(G′)≥30,但χ(G′)>Δ(G′)+3.令图G是一个满足Δ(G)≤Δ(G′)=Δ,g(G)≥5,χ(G)>Δ+3且|E(G)|+|V(G)|最小的平面图,则图G是(Δ+3)-临界图.显然,图G是连通图且δ(G)≥2.记ε=1/5.用权转移方法证明G是不存在的.对任意x∈V∪F,构造一个权函数w(x),其中当v∈V时,w(v),当f∈F时,w(f)=d(f)-5.根据连通平面图的Euler公式|V|+|F|-|E|=2及度和公式,有下面根据G的结构性质,在保持总权和不变的情况下,对G中的点和面的权按一定规则进行转移,得到一个新的权函数w*(x).下面将证明:对任意x∈V∪F,都有w*(x)≥0,从而得出如下矛盾:这个矛盾说明G不存在,从而定理1是成立的.权转移分2步进行.第1步:对∀x∈V∪F,设置初始权为w(x).运用一些转权规则,将证明除一些5-点、6-点外的任意顶点和面得到的新权w′(x)≥0.第 2 步:将对于这些权小于零的顶点定义新的转权规则,得到的新权记为w*(x)，并将证明w*(x)≥0.定义以下权转移规则:R1:3≤d(v)≤9的点v给相邻的轻2-点转权1;R2:5≤d(v)≤9的点v给相邻的重2-点转权R3:若4≤d(v)≤9,则v给相邻的3(1)-点转权ε;R4:若3≤d(v)≤9,则v给相邻的轻3(0)-点转权R5:每个10+-点v给相邻的9--点转权.注意到:若d(v)≥Δ-5≥25,则v给相邻的9--点至少转权若d(v)≥10,则v向9--点至少转权1.运用第1步转权规则之后,将对∀x∈V(G)∪F(G)的新权记为w′(x).记 f是G的k-面.因为k≥5,所以对∀f∈F(G),w′(f)=d(f)-5≥0.对于顶点v,设d(v)=k,则由性质2知k≥2.1)k=2,w(v)=-2.记N(v)={x,y},不妨设d(x)≤d(y).若v是轻2-点,则由R1,R5知,w′(v)≥-2+1+1=0.否则,v是重2-点,即d(x)+d(y)≥Δ+5.当d(x)≥10时,由R5知,w′(v)≥-2+1+1=0;当5≤d(x)≤9时,d(y)≥Δ-4,由R2,R5知,w′(v).记N(v)={x,y,z},不妨设d(x)≤d(y)≤d(z).若d(x)=2,则D(x)≤Δ+3.所以,x是轻2-点.由性质3知,D(v)≥Δ+3+d(v)=Δ+6.又因为d(x)=2,所以d(y)+d(z)≥Δ+4.因此,或有d(y)≥10且d(z)≥10,由R1,R5知,w′(v)或有4≤d(y)≤9且d(z)≥Δ-5,由R1,R3,R5知,w′(v).否则,d(x)≥3.当d(z)≥10时,由R3,R5知,w′(v)当max{d(x),d(y),d(z)}≤9时,v是轻3(0)-点,由性质4知,x,y,z都不是轻3(0)-点.由R4知,w′(v).3)k=4,w(v)=1.因为d(v)=4,所以与v相邻的每个2-点都是轻2-点.若n2(v)=0,则由R3,R4知,w′(v)≥1-4×ε≥0.若n2(v)≥1,则由性质3知,D(v)≥Δ+7,所以.当且n3(v)=0时,v至少相邻1个10+-点,由R1,R5知,w′(v)≥1-2×1+1=0;当且n3(v)=1时,v相邻1个Δ-点,由R1,R3～R5知,w′(v)当时,易知v至少相邻1个10+-点,由R1,R3～R5知,w′(v)≥1-1-2×ε+1>0..①.当时,由R2 知,当时,由R2～R4知,当时,由R2～R4知,.②(v)≥1.由性质3知,D(v)≥Δ+8,所以n2(v)≤4.当2≤n2(v)≤3时,v至少相邻1个10+-点,由R1,R3～R5知,.当n2(v)=4 时,v相邻1个Δ-点,当时,由R1～R2,R5知,当时,由R1,R5知,ε.当时,由R1,R3,R5知,.5)k=6,w(v)=4.若,则由R2～R4知,ε.否则,(v)≥1,由性质3知,D(v)≥Δ+9,所以n2(v)≤5.当n2(v)=5时,v至少相邻1个(Δ-1)+-点,由R1～R2,R5知,当n2(v)=4时,v至少相邻1个10+-点,由R1～R5知,w′(v)≥4-4×1-ε+1>0;当n2(v)≤3时,v 至少相邻1个8+-点,由R1～R5知,w′(v)≥4-3×1-2ε>0..若,则由R2～R4知,.否则,(v)≥1.由性质3知,D(v)≥Δ+10,所以n2(v)≤6.当n2(v)=6时,v至少相邻1个(Δ-2)+-点,由R1～R2,R5知,当n2(v)≤5时,由R1～R4知,w′(v).7)k=8,w(v)=7.若,则由R2～R4知,.否则,(v)≥1.由性质3知,D(v)≥Δ+11,所以n2(v)≤7.当n2(v)=7时,v至少相邻1个(Δ-3)+-点,由R1～R2,R5知,当n2(v)≤6时,由R1～R4知,w′(v)≥7-6×1-2ε>0..若,则由R2～R4知,.否则,(v)≥1,由性质3知,D(v)≥Δ+12,所以n2(v)≤8.因此,由R1～R4知,w′(v).9)k≥10,由R5知,.在运用第1次权转移规则后,对∀x∈V(G)∪F(G),除了一些5-点和6-点外,其余的顶点和面都有非负的权值.称这些权值可能为负的5-点和6-点为坏5-点和坏6-点;称权值非负的顶点为好点.综上讨论,存在4种可能的坏5-点和坏6-点.对uv∈E(G),若d(u)≥10,d(v)≥10,则称uv为特殊边.第2次权转移规则R6～R8:R6:每个10+-点v通过特殊边给关联面 f转权;R7:每个2≤k≤9的k-点v将多余的权值平均转给每个关联面;R8:通过R6,R7转权后,每个5+-面 f将多余的权值平均转给面 f上可能的坏5-点和坏6-点.运用第2次转权规则之后,把∀x∈V(G)∪F(G)的新权记为w*(x).断言1 设v是(v)=4的坏5-点,记N(v)={x,y,z,u,w},其中x,y,z,u,w按逆时针排列.记d(w)=d(x)=d(y)=d(z)=2,w1,x1,y1,z1为w,x,y,z的不同于v的另一个邻点.设v恰好关联5个 5-面,记 f=[uvww1u1],其中u1∈N(u)∩N(w1).若4≤d(w1)≤5,则d(u1)≥3.证明因为v关联5个5-面,所以{w1x1,x1y1,y1z1,z1u2,u1w1}⊆E(G),其中u1,u2∈N(u).记 f=[uvww1u1].因为(v)=4,所以x为轻2-点.由轻2-点的定义知,D(x)≤Δ+4.又因为d(v)=5,所以x1 为(Δ-1)--点.同样,y1,z1,w1均为(Δ-1)--点.由性质3 知,d(u)=Δ,再由性质2知,min{d(w1),d(x1),d(y1),d(z1)}≥3.反证法若4≤d(w1)≤5,则可设d(u1)=2.由G的极小性知,G-vw有一个(Δ+3)-injective染色c.先擦去v和w的颜色.若|c(N2(v))|≤Δ+2,则可以把c延拓到整个图G.因为w的禁用色至多是8,所以w可以被正常染好.否则,设|c(N2(v))|≥Δ+3.因为|N2(v)|=Δ+3,所以|c(N2(v))|=Δ+3.考虑 u1,易知擦去v和w的颜色之后,|c(N2(u1))|≤Δ+1,可以用c(u1)染v,再把u1染好,最后染w.这样,c就成为G的一个(Δ+3)-injective染色.与假设矛盾.断言1证毕.下面分4种情形讨论坏5-点和坏6-点最终的权.1)设v是(v)=4且相邻一个Δ-点的坏5-点,通过第1次转权后,w′(v)≥-ε.记N(v)={x,y,z,u,w},其中x,y,z,u,w按逆时针排列.不妨设d(w)=d(x)=d(y)=d(z)=2,且d(u)=Δ,与断言1的证明类似,有max{d(w1),d(x1),d(y1),d(z1)}≤Δ-1且min{d(w1),d(x1),d(y1),d(z1)}≥3.若v关联6+-面,且记 f是其中的一个 6+-面,则面 f中必定有2个点属于{x,y,z,u,w},且这2个点必定不是坏5-点和坏6-点.所以,面f中至多有d(f)-2个坏5-点和坏6-点,由R8知, f至少可以给v转权.所以,w*.若v不关联6+-面,则v恰好关联5个5-面.有{w1x1,x1y1,y1z1,z1u2,u1w1}⊆E(G),其中u1,u2∈N(u).记f1=[uvww1u1],f2=[zvuu2z1],f3=[yvzz1y1],f4=[xvyy1x1].若d(u1)≥10,则uu1是特殊边,由R6 知,面 f1至少可以从u,u1获得权1.因为v是面 f1中唯一的坏5-点或坏6-点, 所以由 R8 知, v从面 f1 获得权 1.因此,w*(v)≥w′(v)+1>0.类似地,若d(u2)≥10,则w*(v)≥0.下面仅考虑d(u1)≤9,d(u2)≤9.①w1和z1都是10+-点.当d(w1)≥10时,因为d(u1)≥2,所以在第1步权转移之后ε.由R7知,u1给每个关联的面转权,所以u1至少给每个关联面转权.由于面 f1中只有v是坏5-点或坏6-点,因此由 R8知,v从面 f1中获得权.同样,当d(z1)≥10时,顶点u2给面 f2至少转权,而面 f2中只有v是坏 5-点或坏6-点,所以由R8知,v从面f2中获得权.因此,w*.②w1和z1中至少有1个为9--点,不妨设3≤d(z1)≤9.因为z是轻2-点,所以由性质3知,D(z1)≥Δ+3+d(z1).若d(z1)=9,则D(z1)≥Δ+12,从而n2(z1)+n3(z1)≤8.由断言1知,3≤d(y1)≤Δ-1.计算z1在第1次转权之后的权w′(z1):当n2(z1)=8时,当n2(z1)=7且n3(z1)=0时,z1相邻1个10+-点,当n2(z1)=7且n3(z1)=1时,z1相邻1个(Δ-5)+-点,当n2(z1)≤6时,.综上,第1次转权结束后,.由R7知,z1至少给每个关联面转权,所以z1至少给面 f2 转权.因为面 f2上只有v是坏5-点或坏6-点,所以由R8知,顶点v从面 f2中获得权.因此,w*.若d(z1)=8,则D(z1)≥Δ+11,从而n2(z1)+n3(z1)≤7.由断言1知,3≤d(y1)≤Δ-1.计算z1在第1次转权之后的权w′(z1):当n2(z1)=7时,当n2(z1)=6且n3(z1)=0时,z1相邻1个10+-点,w′(z1)≥7-6×1+1=2;当n2(z1)=6且n3(z1)=1时,z1相邻1个(Δ-4)+-点,当n2(z1)≤5 时,.综上,第1次转权结束后,.由R7知,z1至少给每个关联面转权.因此,z1分别给面 f2和 f3转权.因为面 f2和 f3中只有v是坏 5-点或坏6-点,所以由R8知,顶点v分别从面 f2和 f3中获得权.因此,w*.若d(z1)=7,则D(z1)≥Δ+10,从而n2(z1)+n3(z1)≤6.由断言1知,3≤d(y1)≤Δ-1.计算z1在第1次转权之后的权w′(z1):当n2(z1)=6时,当n2(z1)=5且n3(z1)=0时,z1相邻1个10+-点,当n2(z1)=5且n3(z1)=1时,z1相邻1个(Δ-3)+-点,当n2(z1)≤4 时,.综上,第1次转权结束后,.由R7知,z1至少给每个关联面转权.由于v 恰好关联5个5-面且d(z)=2,易知z1关联的面中有2个面恰好是与v关联的5-面,所以z1分别给面 f2和 f3转权.因为面 f2和 f3中只有v是坏5-点或坏6- 点,所以由R8知,顶点v分别从面 f2和 f3中获得权.因此,w*.若d(z1)=6,则D(z1)≥Δ+9,从而n2(z1)+n3(z1)≤5.由断言1知,3≤d(y1)≤Δ-1.若n2(z1)=5,则d(y1)=Δ-1.通过第1次权转移后,,由R7知,y至少给每个关联面转权.所以,y至少给面 f3和 f4分别转权.因为面 f3和 f4上只有v是坏5-点或坏6-点,所以由R8知,顶点v从面 f3和 f4中分别获得权.因此,w*.否则,n2(z1)≤4.计算z1在第1次转权之后的权w′(z1):当n2(z1)=4且n3(z1)=0时,z1相邻1个10+-点,w′(z1)≥4-4+1=1;当n2(z1)=4且n3(z1)=1时,z1相邻1个(Δ-2)+-点,当n2(z1)=3且n3(z1)=0时,w′(z1)≥4-3×1=1;当n2(z1)=3且n3(z1)≥1时,z1至少相邻1个10+-点,当n2(z1)≤2时,.综上,第1次转权结束后,w′(z1)≥1.由R7知,z1至少给每个关联面转权.因此,z1分别给面 f2和 f3转权.因为面 f2和 f3中只有v是坏5-点或坏6- 点,所以由R8知,顶点v分别从面 f2和 f3中获得权.因此,w*.若d(z1)=k(k∈{4,5}),则D(z1)≥Δ+3+k,从而n2(z1)+n3(z1)≤k-1.由断言1和对称性知,d(u2)≥3.因为3≤d(y1)≤Δ-1,所以n2(z1)≤k-2.若n2(z1)=k-2,从而d(y1)+d(u2)≥Δ+7-k.由于3≤d(u2)≤9,所以d(y1)≥Δ-2-k>10.通过第1次权转移后,,由R7知,y至少给每个关联面转权.所以,y至少给面 f3,f4分别转权.因为面 f3和f4上只有v是坏5-点或坏6-点,所以由R8知,顶点v从面 f3,f4中分别获得权.因此,.若 n2(z1)=k-3,则z1至少相邻1个10+-点,.由R7知,z1至少给每个关联面转权,所以z1分别给面 f2和 f3转权.因为面 f2和 f3上只有v是坏5-点或坏6- 点,所以由R8知,顶点v从面 f2和 f3中分别获得权.因此,w*.若n2(z1)=k-4,则只需考虑 k=5,即n2(z1)=1.当n3(z1)=0时,当1≤n3(z1)≤3 时,z1至少相邻1个10+-点,.由R7知,z1至少给每个关联面转权,所以z1至少给面 f2转权.因为面 f2上只有v 是坏5-点或坏6-点,所以由R8知,顶点v从面 f2中获得权.因此，w*.若d(z1)=3,则D(z1)≥Δ+6,从而d(y1)+d(u2)≥Δ+4.由于d(u2)≤9,所以d(y1)≥Δ-5.通过第1次权转移后,,由R7知,y至少给每个关联面转权.所以,y 分别给面 f3和f4转权.因为面 f3和 f4上只有v是坏5-点或坏6-点,所以由R8知,顶点v从面 f3和 f4中分别获得权.因此,w*2)设v是(v)=5的坏5-点,通过第1次转权后,w′(v)≥-5ε.记N(v)={x,y,z,u,w},其中x,y,z,u,w按逆时针排列,w1,x1,y1,z1,u1为w,x,y,z,u不同于v的另一个邻点.w,x,y,z,u为2-点,根据重2-点的性质得w1,x1,y1,z1,u1均为Δ-点.记f1=[uvww1…u1], f2=[wvxx1…w1], f3=[xvyy1…x1],f4=[yvzz1…y1],f5=[zvuu1…z1].若v至少关联1 个5-面,则w1x1,x1y1,y1z1,z1u1,u1w1中至少有1条边属于E(G),易知这条边是特殊边.不妨设 f1是5-面,u1w1是f1=[wvuu1w1]上的特殊边,由R6知,面 f1可以从u1,w1中至少获得的权是.因为面 f1中只有v是坏 5-点或坏6-点,所以由R8知,顶点v从面 f1中获得权.因此,w*.否则,v不关联5-面,即 f1,f2,f3,f4,f5都是6+-面.因为w,x,y,z,u为2-点且w1,x1,y1,z1,u1均为Δ-点,所以x,y,z,u,w,x1,y1,z1,u1,w1都是好点.又因为 f1, f2,f3, f4, f5中的每个面上至少有4个好点,所以面fi(i∈{1,2,…,5})上至多有d(fi)-4个坏点.由R8知,每个面 fi至少可以给v转权.因此,.3)设v是且相邻1个3-点的坏5-点,通过第1次转权后,ε.N(v)={x,y,z,u,w},其中x,y,z,u,w按逆时针排列,w1,x1,y1,z1,u1为w,x,y,z,u不同于v的另一个邻点.不妨设w,x,y,z为2-点,根据重2-点的性质得w1,x1,y1,z1均为Δ-点.记f1=[vxx1…w1w], f2=[xvyy1…x1],f3=[zvyy1…z1].若 f1, f2, f3中至少有1个5-面,则w1x1,x1y1,y1z1中至少有1条边属于E(G),易知这条边是特殊边.不妨设w1x1是 f1=[vxx1w1w]上的特殊边,由R6知,面 f1至少可以从z1,w1中获得权.因为面f1上只有v是坏5-点或坏6-点,所以由R8知,顶点v从面f1中获得权.因此，w*.否则, f1, f2, f3都不是5-面,即它们都是6+-面,但 f1, f2, f3上至少有4个好点.由R8知, f1, f2, f3分别向v转权.因此,w*.4)设v是(v)=6的坏6-点,通过第1次转权后,w′(v)≥-ε.N(v)={x,y,z,u,w,p},其中x,y,z,u,w,p按逆时针排列,w1,x1,y1,z1,u1,p1 为w,x,y,z,u,p不同于v的另一个邻点.w,x,y,z,u,p为2-点,根据重2-点的性质得w1,x1,y1,z1,u1,p1均为(Δ-1)+-点.若v至少关联1个5-面,不妨设 f=[uvww1u1]是一个5-面,则w1u1是特殊边.由R6知,面 f至少可从u1,w1中获得权.因为面 f中只有v是坏5-点或坏6-点,所以由R8知,顶点v至少从面 f中获得权.因此,w*.否则,v不关联5-面,即v关联6个6+-面.记f ′=[uvww1…u1]是一个6+-面.因为面f ′上w,w1,u,u1是好点,所以面f ′上至多有d(f)-4个坏点.由R8知,面f ′至少可以给v转权.因此,w*.最后,对于特殊边e=uv中的顶点u,根据R5,u不给v转权,即相对于顶点u剩余权,而根据R6,u通过边e分别给与边e相邻的2个面转权,因此顶点u最终仍有w*(u)≥0.通过2次权转移就检验了对任意x∈V(G)∪F(G),都有w*(x)≥0,从而得到矛盾.定理1证毕.本文讨论了围长至少为5的平面图的injective染色问题,证明了:若图G是g(G)≥5,Δ(G)≥30的平面图,则χi(G)≤Δ(G)+3.根据文献[7]的结论和本文结果,下面这个问题是有意义的,即:对于g(G)≥5的平面图G,探讨最小的正整数Δ0,使得当Δ(G)≥Δ0时,有χi(G)≤Δ(G)+3.【相关文献】[1]Hahn G,Kratochvíl J,Sirá J,et al.On the injective chromatic number of graphs[J].Discrete Math,2002,256(1/2):179-192.[2]Doyon A,Hahn G,Raspaud A.Some bounds on the injective chromatic number of graphs[J].Discrete Math,2012,310(3):585-590.[3]Cranston D,Kim S,Yu G.Injective colorings of graphs with low averagedegree[J].Algorithmica,2010,60(3):553-568.[4]Cranston D,Kim S,Yu G.Injective colorings of sparse graphs[J].DiscreteMath,2010,310(21):2965-2973.[5]Bu Y,Chen D,Raspaud A,et al.Injective coloring of planar graphs[J].Discrete Appl Math,2009,157(4):663-672.[6]Dong W,Lin W.Injective coloring of planar graphs with girth 6[J].DiscreteMath,2013,313(12):1302-1311.[7]Dong W,Lin W.Injective coloring of plane graphs with girth 5[J].DiscreteMath,2014,315/316(12):120-127.。

[Δ]（G）=8且不含4-圈的平面图的完备染色平面图是指能够在平面上画出来的图形，不会有交叉或重叠的边。

染色是指给图中的顶点分配颜色，使得相邻的顶点颜色不同。

完备染色是指对于图中的每个顶点都能给出一个颜色，使得相邻的顶点颜色不同。

在一个平面图中，如果存在一个4-圈（也称为四边形环），则无法进行完备染色。

因为四个相邻的顶点形成一个4-圈，在没有其他顶点被考虑的情况下，这四个顶点无法被染色，因为它们都相邻且无法用相同的颜色进行染色。

现在我们来讨论没有4-圈的平面图的完备染色。

如果一个平面图没有圈，那么它只能是一条直线或一个单独的顶点，因此它总是可以进行完备染色。

当平面图有圈时，如果它没有4-圈，则可以进行完备染色。

证明如下：假设有一个平面图G，它没有4-圈。

我们采用数学归纳法来证明完备染色存在。

1. 当G只有一个顶点时，显然可以进行完备染色。

2. 假设对于顶点数小于等于k的平面图，都可以进行完备染色。

3. 考虑一个顶点数为k+1的平面图G'。

我们选择一个顶点v，它的度数至少为3。

因为如果图中所有顶点的度数都小于3，则存在一个4-圈。

我们选择一个与v相邻的顶点u，以及u的两个邻居w和x。

4. 我们移除u、w和x，并且将v和u之间的边去掉，得到的图记为G''。

显然G''是一个顶点数小于等于k的平面图。

根据假设，G''可以进行完备染色，即存在一种染色方式使得G''中的每个顶点都与相邻顶点颜色不同。

5. 现在我们来考虑如何给G中的顶点进行染色。

由于v与u相邻，我们不能直接将v 染色为与u相邻的颜色。

但是我们可以观察到，u的度数至少为3，即u至少与另外两个顶点相邻，分别为w和x。

我们可以将v染色为与u、w和x都不同的颜色。

6. 现在我们只需要给G''中的顶点进行染色。

由于G''是一个顶点数小于等于k的平面图，根据假设，我们可以进行完备染色。