围长至少是7的平面图的均匀染色王心洁目录TOC\o"1-2"\h\z\uHYPERLINK\l"_Toc39680845"摘要PAGEREF_Toc39680845\h1HYPERLINK\l"_Toc39680846"AbstractPAGEREF_Toc39680846\h1HYPERLINK\l"_Toc39680847"一、引言PAGEREF_Toc39680847\h2HYPERLINK\l"_Toc39680848"（一）基本概念与符号PAGEREF_Toc39680848\h2HYPERLINK\l"_Toc39680849"（二）图的均匀染色问题的研究现状PAGEREF_Toc39680849\h3HYPERLINK\l"_Toc39680850"（三）本文的主要内容与结果PAGEREF_Toc39680850\h5HYPERLINK\l"_Toc39680851"二、权转移方法PAGEREF_Toc39680851\h6HYPERLINK\l"_Toc39680852"三、平面图的均匀染色问题PAGEREF_Toc39680852\h7HYPERLINK\l"_Toc39680853"（一）基本引理PAGEREF_Toc39680853\h7HYPERLINK\l"_Toc39680854"（二）极小反例的结构特点PAGEREF_Toc39680854\h10HYPERLINK\l"_Toc39680855"（三）定理2.1.1的证明PAGEREF_Toc39680855\h23HYPERLINK\l"_Toc39680856"四、可进一步研究的问题PAGEREF_Toc39680856\h26HYPERLINK\l"_Toc39680857"参考文献PAGEREF_Toc39680857\h27HYPERLINK\l"_Toc39680858"致谢PAGEREF_Toc39680858\h29PAGE\*MERGEFORMAT39围长至少是7的平面图的均匀染色王心洁摘要设G=(V,E)，图的正常点染色是指对图G上所有的点进行染色，使得相邻两个点所染的颜色不同。图的均匀点染色是指对图G的一个正常点染色，使得每种颜色所对应的点的数目至多相差1。图G是m-均匀可染的是指存在一个映射f:VG→{1,2,…,m}，使得当uv∈E(G)时f(u)≠f(v)，并且满足V1≤V2≤…≤Vm≤V1+1。图G的均匀色数阈值Xeq*(G)是指一个最小的整数m，使得对任意的n≥m，图G都是n-均匀可染的。本文采用权转移的方法证明最小度至少是2，围长至少是7的平面图的均匀色数阈值Xeq*(G)小于等于7。关键词：平面图；均匀染色；权转移Equitablecoloringofplanargraphswithgirthatleast7XinjieWangAbstractGivenagraphG=(V,E),apropervertexcoloringofGisacoloringofverticesofGsuchthatthecolorsofthetwoadjacentverticesaredifferent.AnequitablevertexcoloringofGisapropervertexcoloringsuchthatthesizesofcolorclassesdifferbyatmostone.IfGism-equitablecoloring,thenthereisamappingf:VG→{1,2,…,m}suchthatf(u)≠f(v)ifuv∈E(G),andV1≤V2≤…≤Vm≤V1+1.TheequitablechromaticthresholdXeq*(G)ofGisthesmallestintegermsuchthatGism-equitablecoloringforalln≥m.Withthedischargingmethod,theresultthateveryplanargraphwithminimumdegreeatleast2andgirthatleast7hasXeq*(G)≤7isverified.Keywords:planargraphs;equitablecoloring;discharging一、引言图论是数学领域中实用价值很高的学科之一，起源于哥尼斯堡七桥问题，而图的染色问题作为图论的一个重要分支，最早可以追溯到18