极大平面图的结构与着色理论(4)σ-运算与Kempe等价类

设G是一个k-色图,若G的所有k-着色是Kempe等价的,则称G为Kempe图。表征色数33的Kempe图特征是一尚待解决难题。该文对极大平面图的Kempe等价性进行了研究,其主要贡献是:(1)发现导致两个4-着色是Kempe等价的关键子图为2-色耳,故对2-色耳的特征进行了深入研究;(2)引入σ-特征图,清晰地刻画了一个图中所有4-着色之间的关联关系,并深入研究了σ-特征图的性质;(3)揭示了4-色非Kempe极大平面图的Kempe等价类可分为树型,圈型和循环圈型,并指出这3种类型可同时存在于一个极大平面图的4-着色集中;(4)研究了Kempe极大平面图特征,给出了该类图的多米诺递推构造法,以及两个Kempe极大平面图猜想。

极大外平面图中树的 Anti-Ramsey 数

对给定的边染色图 G,如果图 G 的每条边颜色都不一样,则称图 G 是彩虹的。Anti-Ramsey 数 AR(K, F ) 是最大的正整数 k,使得图 K 的任意 k-边染色中,图 K 不包含族 F 中任意的 彩虹图。近些年来,图的 anti-Ramsey 数吸引了很多图论学者的关注,其中平面图中图的 anti- Ramsey 数得到了深入的研究。Jiang 和 West 研究了 k 条边的树在完全图上的 anti-Ramsey 数,而 k 条边的树在平面图中的 anti-Ramsey 数的结论不多。在本文中,我们研究了 k 条边的 树在极大外平面图中的 anti-Ramsey 数,得到了它的上下界。

极大外平面图的Wiener指标的上下界

外平面图是具有平面嵌入的平面图,其中每个顶点位于外部区域的边界上.若通过添加边获得的图不是外平面图,则此时的外平面图是极大外平面图.图G的Wiener指标是所有顶点对之间距离的总和.证明了对于n个顶点的极大外平面图G,有W(K1_P_(n−1))≤W(G)≤W(P_(n)^(2)),其中K_(1)P_(n−1)是通过将一个点和路P_(n−1)的每个顶点相连得到的图,P_(n)^(2)是路的平方图.

极大平面图理论研究进展

四色猜想是指平面图的色数不超过4.实际上,四色猜想只需证明对极大平面图成立即可.正因为如此,从1891年至今,有众多学者从不同的角度展开了对极大平面图的研究.该文拟对其中的一些重要成果进行较为详细的综述,主要包括极大平面图的度序列问题、Hamilton性、色多项式、生成运算系统、计数、翻转运算、分解与覆盖、生成树和算法等方面.在总结极大平面图研究现状的基础上,提出了一些与着色相关的问题,这些问题意在探索极大平面图的结构与着色之间的关系,有助于对四色问题的进一步研究.

极大外平面图的星边染色

如果图G的一个正常边染色使得G中没有长为4的路或4-圈是2-边染色的,则称此染色是G的一个星边染色.对G进行星边染色所需的最少颜色数称为G的星边色数,记作X′_s(G).该文证明了最大度为4的极大外平面图的星边色数等于6,对任一n(≥8)阶极大外平面图G_n,有6≤X′_s(G_n)≤n-1成立,并且上界和下界都是可达的.

极大平面图结构研究

为采用常规数学方法研究“四色问题”，本文先对极大平面图的结构进行分析提出了极大平面图的判断定理。

极大平面图的结构与着色理论 (3)纯树着色与唯一4-色极大平面图猜想

一个极大平面图若是从K_4出发,不断地在三角面上嵌入3度顶点得到的,则称此极大平面图为递归极大平面图。唯一4-色极大平面图猜想是指:一个平面图是唯一4-可着色的当且仅当它是递归极大平面图。此猜想已有43年历史,是图着色理论中继四色猜想之后另一个著名的未解猜想。为此,该文相继深入研究了哑铃极大平面图与递归极大平面图的结构与特性,结合该系列文章(2)的扩缩运算,给出了证明唯一4-色极大平面图猜想的一种思路。

极大平面图的结构与着色理论 (2)多米诺构形与扩缩运算

业已证明四色猜想的数学证明可归结为刻画4-色漏斗型伪唯一4-色极大平面图的特征。为刻画此类极大平面图的结构特征,本文提出一种构造极大平面图的方法——扩缩运算。研究发现：此方法的关键问题是需要清楚一种构形,称为多米诺构形。文中构造性地给出了多米诺构形的充要条件;在此基础上提出并建立了一个图的祖先图与子孙图理论与构造方法。特别证明了：任一最小度≥4的n（≥9）-阶极大平面图必含（n-2）-阶或（n-3）-阶祖先图;给出极大平面图的递推构造法,并用此方法构造出6~12-阶所有最小度≥4的极大平面图。扩缩运算是本系列文章的基石。

极大平面图的结构与着色理论 (1)色多项式递推公式与四色猜想

该文给出了极大平面图G的色多项式递推计算公式:若d(G)=4,Wv4是G中轮心为v,轮圈为v1 v 2v 3v 4v 1的4-轮,则f(G,4)=f(G1,4)+f(G2,4),其中G1=(G-v)?{v1,v3},G 2=(G-v)?{v2,v4};若d(G)=5,Wv5是G中v为轮心,以v1 v 2v 3v 4v 5v 1为轮圈的5-轮,则f(G,4)=[f(G1,4)-f(G1?{v1 v 4,v1 v 3},4)]+[f(G2,4)-f(G 2?{v 3v 1,v 3v 5},4)]+[f(G3,4)-f(G 3?{v1 v 4},4)],其中G1=(G-v)?{v 2,v 5},G 2=(G-v)?{v 2,v4},G 3=(G-v)?{v3,v5},"?"表示收缩运算;进而讨论了使用公式证明四色猜想的应用:将四色猜想转化成研究一种特殊图类:4-色漏斗型伪唯一4-色极大平面图。

正则极大平面图的邻强边染色

设G是一个简单图,若图G的一个k-正常边染色f满足对任意的uv∈E(G),都有C(u)≠C(v),则称f为G的一个邻强边染色,简称k-ASEC,并称x_(as)′(G)=min{k|G存在k-ASEC},为G的邻强边色数.其中C(u)={f(uv)|uv∈E(G)}.该文研究了一类正则极大平面图的邻强边染色,给出了着色方案,求解出其邻强边色数.

关于极大平面图自同构群的几个定理和生成算法

本文对极大平面图及其若干四着色通过其二色子图间的同构定义了四着色的同构 (定义6、7), 并给出相关定理. 定理A: 若G有同构四着色C1、C2, 置换σ是相应同构置换, 则σ是G的自同构. 定理B: G和其四着色C, 置换σ是其各二色子图共同的自同构, 则σ也是G的自同构.据此, 给出了求解G的自同构群的算法. 一个四连通或五连通的G, 其自同构问题被转化为三对子图的同构、自同构问题.这些子图的连通度通常为2. 点数仍为p, 边数仅为G的三分之一. 对相当广泛的图类,子图可为树或路,使问题的难度大为简化.文中给出两个具体图例. 说明了对数十个点的G, 在普通微机上(如133主频, 16M 内存)

着五色极大平面图的对偶2～3色子图及五色点消减的实验研究

本文对已着五色极大平面图定义了对偶２～３色子图，并将［１］中着四色极大平面图对偶二色子图的两个定理、四个推论推广到此种情况．根据对偶２～３色子图结构属性，作者实现了一个四着色算法．算法要点是，先对图着五色，再轮番对六个三色子图重新着（３或２）色，以消减五色点，直至五色点数为零．本文通过例图说明了这种四着色步骤。

极大外平面图边面全色数的注记

设G是2-连通的平面图.证明了若G是最大度Δ(G)=5的极大外平面图，则其边面全色数χef(G)=5.

关于高度极大外平面图的4染色

从最大度的角度讨论两个极大外平面图的公共４染色，证明了当Ｇ是以ｒ个顶点的圈Ｑｒ为标定界环的极大外平面图且△（Ｇ）≥ｒ－２，Ｇ’是以Ｑｒ为标定界环的任一极大外平面图时，Ｇ和Ｇ’有公共４染色．从而证明了四色定理的等价命题在给定条件下成立．

关于(4,6)-正则极大平面图的构造

当图的顶点数n>12时不存在正则极大平面图.文献[2]提出了(r,k)-正则极大平面图的概念,并讨论了(5,6)-正则极大平面图的存在性.本文讨论了(4,6)-正则极大平面图,得到了(4,6)-正则极大平面图的存在条件及构造方法.

极大平面图的局部结构及其着色特性

本文在文献［１］的基础上，进一步研究了极大平面图层圈结构中的几种典型局部结构及着色特性。这些局部结构包括轮图（由点ｖ及Ｄ１（ｖ）生成），弦弧圈（由Ｄｒ（ｖ）生成），圈村图（由Ｄｒ－１与Ｄｒ生成）及平行圈和层间结构（由Ｄｉ与Ｄｉ＋１生成）。这些结构的多数可以简单地确定具有３色性或４色性。最后，讨论了任意极大平面图表示为两个典型局部结构的某种二元分解问题。

极大平面图的构造

重新给出了构造极大平面图的删边加点法的概念,分析了极大平面图的结构,给出了极大平面图的构造定理,并以12阶极大平面图为例说明了这个定理具有很强的可操作性.

极大外平面图的邻强边色数

本文证明了对极大外平面图 G,Δ(G) χ′as(G)≤ Δ(G) +1,且 χ′as(G) =Δ(G) +1,当且仅当存在两个最大度点相邻 .其中Δ (G)、χ′as(G)分别表示图 G的最大度和邻强边色数 .

构造极大平面图的三种方法

对极大平面图的构成方法做了进一步的研究，提出了三种构成方法：规范的“加点法”与“删步法”以及非规范的“任意法”，并对三种构成方法进行了比较分析。同时对同阶非同构极大平面图的计数问题进行了理论分析。以命题形式给出了８个结论，这些结论对研究极大平面图的点着色问题有其理论与应用价值。

两个只有路型二色子图的极大平面图

本文证明了极大平面图g9D和g12A,其每个四着色的每个二色子图都是路.并猜测在全部无分离三圈的极大平面图中这是仅有的两个图.