一、一类4——可着色的极大平面图(论文文献综述)
崔福祥,杨超,叶宏波[1](2020)在《图在约束条件下的邻点可区别全染色》文中指出设f:V(G)∪E(G)→{1,2,…,k}是简单图G的一个正常k-全染色.令C(f,u)={f(e):e∈Ne(u)},C[f,u]=C(f,u)∪{f(u)},C2[f,u]=C(f,u)∪{f(x):x∈N(u)}∪{f(u)}.N(u)表示顶点u的邻集,Ne(u)表示与顶点u的相关联的边集合.令C[f;x]={C(f,x);C[f,x];C2[f,x]},对任意的边xy∈E(G),C[f;x]≠C[f;y]表示C(f,x)≠C(f,y),C[f,x]≠C[f,y],C2 [f,x]≠C2[f,y]同时成立.对任意的边xy∈E(G),如果有C[f;x]≠C[f;y]成立,则称f是图G的一个k-(3)-邻点可区别全染色(简记为k-(3)-AVDTC).图G的(3)-邻点可区别全染色中所需最少的颜色数叫做G的(3)-邻点可区别全色数,记为χ"(3)as(G).文章研究(2,2)-递归极大平面图的(3)-邻点可区别全染色,并确定此类图的(3)-邻点可区别全色数.此外,提出了简单图的(3)-邻点可区别全染色猜想.
李泽鹏[2](2019)在《唯一可着色图研究进展》文中指出唯一可着色图是指在不考虑颜色置换的情况下只有一个正常着色的图.判断一个图是否为唯一可着色的问题是NP-难的.文章从结构性质、存在性、构造等方面对唯一可着色图,特别是唯一3-可着色平面图的研究进行了介绍,并总结了一些目前尚未解决的问题.
刘小青,许进[3](2017)在《4-正则图着色的Kempe等价性》文中指出给定一个图G及它的一个正常顶点着色f,G中任意两种颜色的顶点导出子图称为G的一个2-色导出子图,该2-色导出子图的分支称为G的一个2-色分支。Kempe变换是指将图G的某个2-色分支实施颜色互换。若两个着色之间可通过若干次Kempe变换达到对方,则这两个着色是Kempe等价的。Mohar猜想当k33时,对于任意的连通k-正则图G,若G不是完全图,则G的所有k-着色是Kempe等价的。Feghali等人解决了k=3时的情况,当k34时,此猜想尚未解决。该文研究了k=4时的情况,证明了:(1)若G是一个连通度小于3的4-正则图,则G的所有4-着色是Kempe等价的;(2)若G是4-正则图,且含有与4-轮或近5-阶完全图同构的子图,则G的所有4-着色是Kempe等价的;(3)若G是一个3-连通4-正则图,且G存在一个顶点x和一个4-着色f,满足x的邻域中有3个或4个顶点在f下着相同颜色,则G的所有4-着色是Kempe等价的。
许进,刘小青[4](2017)在《Kempe变换理论研究进展》文中研究说明给定一个图G及它的一个正常顶点着色f,G中所有着两种颜色之一的顶点构成的顶点子集导出的子图称为G的一个2-色导出子图,该2-色导出子图的分支称为G的一个2-色分支。Kempe变换是指将图G的某个2-色分支实施颜色互换。自1879年Kempe引入Kempe变换用于证明四色猜想至今,众多学者从不同的角度对Kempe变换展开了研究。该文总结了Kempe变换的一些基本性质;对已有的一些重要成果进行了较为详细的综述;针对Meyniel定理,即每个平面图的所有5-着色构成一个Kempe等价类,给出了一个新而简短的证明方法;提出了一个与着色类型相关的问题,意在探索不同Kempe等价类之间的关系,以加深Kempe变换的研究。
刘小青,许进[5](2017)在《一种特殊的多米诺扩缩运算》文中指出该文提出一种称为334扩缩运算的多米诺扩缩运算。使用该运算构造了一类特殊的极大平面图——334-型极大平面图,证明了该类图均为树型2-色不变圈着色,且每个4k-阶334-型极大平面图恰有2k-1个2-色不变圈着色及2k-2个树着色。证明了该运算可用于构造纯树着色极大平面图,并提出猜想:若极大平面图G是纯树(纯圈,混合)着色,则对G实施334扩(缩)轮运算后,所得之图仍是纯树(纯圈,混合)着色。
许进[6](2016)在《极大平面图的结构与着色理论 (3)纯树着色与唯一4-色极大平面图猜想》文中研究说明一个极大平面图若是从K4出发,不断地在三角面上嵌入3度顶点得到的,则称此极大平面图为递归极大平面图。唯一4-色极大平面图猜想是指:一个平面图是唯一4-可着色的当且仅当它是递归极大平面图。此猜想已有43年历史,是图着色理论中继四色猜想之后另一个着名的未解猜想。为此,该文相继深入研究了哑铃极大平面图与递归极大平面图的结构与特性,结合该系列文章(2)的扩缩运算,给出了证明唯一4-色极大平面图猜想的一种思路。
任韩,刘兵兵[7](2016)在《曲面上图染色的综述(下)》文中指出曲面地图染色理论作为图论的重要研究领域,是图的染色理论和拓扑图论的交叉学科,也是现代图论中各种各个分支得以发展的源泉之一.该文集中介绍曲面嵌入图的点染色研究中的重要理念,结果,方法以及相关经典成果.其中包括平面上各种染色结果以及他们在曲面上的推广,尤其是Thomassen等人的局部平面化方法;Dirac关于色临界图的开创性工作以及人们在曲面上色临界图的有限性方面的工作,Fisk的构造型证明;曲面上列表染色问题以及大宽度嵌入限制条件下图的3-染色问题.
许进[8](2016)在《极大平面图的结构与着色理论 (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-色极大平面图。
许进[9](2016)在《极大平面图的结构与着色理论(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极大平面图猜想。
许进,李泽鹏,朱恩强[10](2015)在《极大平面图理论研究进展》文中进行了进一步梳理四色猜想是指平面图的色数不超过4.实际上,四色猜想只需证明对极大平面图成立即可.正因为如此,从1891年至今,有众多学者从不同的角度展开了对极大平面图的研究.该文拟对其中的一些重要成果进行较为详细的综述,主要包括极大平面图的度序列问题、Hamilton性、色多项式、生成运算系统、计数、翻转运算、分解与覆盖、生成树和算法等方面.在总结极大平面图研究现状的基础上,提出了一些与着色相关的问题,这些问题意在探索极大平面图的结构与着色之间的关系,有助于对四色问题的进一步研究.
二、一类4——可着色的极大平面图(论文开题报告)
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、一类4——可着色的极大平面图(论文提纲范文)
(1)图在约束条件下的邻点可区别全染色(论文提纲范文)
0 引言 |
1 主要结果及证明 |
2 讨论 |
(2)唯一可着色图研究进展(论文提纲范文)
1 引言及预备知识 |
2 唯一可着色图的性质 |
3 唯一可着色图的存在性和构造 |
4 唯一可着色平面图 |
5 结论与相关研究 |
(4)Kempe变换理论研究进展(论文提纲范文)
1 引言 |
2 K-变换的基本性质 |
3 基于顶点着色的K-变换 |
4 基于边着色的K-变换 |
5 基于着色重构图的K-变换 |
6 Meyniel定理的另一种证明方法 |
7 结束语 |
(7)曲面上图染色的综述(下)(论文提纲范文)
3 列表着色 |
3. 1 列表着色的基本概念和定理 |
3. 2 Erds等的一些成果 |
3. 3 Thomassen等的一些成果 |
3. 4 Mohar等的一些成果 |
4 限定围长和边宽度的图着色 |
4. 1 限定围长的图着色 |
4. 2 限定边宽度的图着色 |
四、一类4——可着色的极大平面图(论文参考文献)
- [1]图在约束条件下的邻点可区别全染色[J]. 崔福祥,杨超,叶宏波. 广州大学学报(自然科学版), 2020(01)
- [2]唯一可着色图研究进展[J]. 李泽鹏. 广州大学学报(自然科学版), 2019(04)
- [3]4-正则图着色的Kempe等价性[J]. 刘小青,许进. 电子与信息学报, 2017(05)
- [4]Kempe变换理论研究进展[J]. 许进,刘小青. 电子与信息学报, 2017(06)
- [5]一种特殊的多米诺扩缩运算[J]. 刘小青,许进. 电子与信息学报, 2017(01)
- [6]极大平面图的结构与着色理论 (3)纯树着色与唯一4-色极大平面图猜想[J]. 许进. 电子与信息学报, 2016(06)
- [7]曲面上图染色的综述(下)[J]. 任韩,刘兵兵. 昆明理工大学学报(自然科学版), 2016(02)
- [8]极大平面图的结构与着色理论 (1)色多项式递推公式与四色猜想[J]. 许进. 电子与信息学报, 2016(04)
- [9]极大平面图的结构与着色理论(4)σ-运算与Kempe等价类[J]. 许进. 电子与信息学报, 2016(07)
- [10]极大平面图理论研究进展[J]. 许进,李泽鹏,朱恩强. 计算机学报, 2015(08)
标签:平面图论文;