关于平面图(3,1)~*-可选性的一个注记(英文)

给出了平面图的一个结构性定理,并证明了每个没有5-圈,相邻三角形,相邻四边形的平面图是(3,1)*-可选色的.     

外平面图的弱边面染色

假设G是一个平面图.如果e1和e2是G中两条相邻边且在关联的面的边界上连续出现,那么称e1和e2面相邻.图G的一个弱边面κ-染色是指存在映射π:E∪F→{1,…,κ},使得任意两个相邻面、两条面相邻的边以及两个相关联的边和面都染不同的颜色.若图G有一个弱边面κ-染色,则称G是弱边面κ-可染的.平面图G的弱边面色数是指G是弱边面κ-可染的正整数κ的最小值,记为χef(G).2016年,Fabrici等人猜想:每个无环且无割边的连通平面图是弱边面5-可染的.本文证明了外平面图满足此猜想,即:外平面图是弱边面5-可染的.     

2-连通的平面图的边面染色

一个平面图G的边面色数χ_(ef)(G)是最小的颜色数,使得G中任意两条相邻的边、两个相邻的面、以及两个关联的边和面都染不同的颜色.本文证明了,若G是?≥16的2-连通平面图,则χ_(ef)(G)=?.这改进了已知结果:若G是?≥24的2-连通平面图,则χ_(ef)(G)=?.     

IC-平面图为第一类图的一个充分条件

图G的一个正常k-边染色是指一个映射Φ:E(G)→{1,2,…,k},使得任意两条相邻的边x,y∈E(G)满足Φ(x)≠Φ(y).使得G具有正常k-边染色的最小正整数k称为图G的边色数,记为χ'(G).著名Vizing定理证明每个简单图G的边色数χ'(G)要么等于最大度Δ(G)要么等于Δ(G)+1.这个定理将所有的图分成了两类:第一类图满足关系式χ'(G)=Δ(G),第二类图满足关系式χ'(G)=Δ(G)十1.本文主要讨论特殊1-平面图的正常边染色问题.1-平面图G是指G能够嵌入到平面上使得G的任意一条边最多被交叉一次.1-平面图G按照上述条件的一种画法称为G的一种1-平面嵌入.所以1-平面图中的每个交叉点w都是由两条边相交所得,从而每个交叉点w都对应着两条相交边,同时也对应着由这两条相交边的四个端点组成的集合ψ(w).如果1-平面图的一个1-平面嵌入中任意两个交叉点w和w'满足ψ(w)∩ψ(w')=Φ,那么称此1-平面图为IC-平面图.在本文中,通过观察分析Δ-临界图和不含相邻弦6-圈的IC-平面图的结构,应用权值转移方法证明了任何最大度为7且不含相邻弦6-圈的IC-平面图G是第一类图.     

外平面图的弱完备染色

假设G=（V,E,F）是一个平面图。如果e₁和e₂是G中两条相邻边且在关联的面的边界上连续出现,那么称e₁和e₂面相邻。图G的一个弱完备k-染色是指存在一个从V ∪ E ∪ F到k色集合{1, …, K}的映射,使得任意两个相邻点,两个相邻面,两条面相邻的边,以及V ∪ E ∪ F中任意两个相关联的元素都染不同的颜色。若图G有一个弱完备k-染色,则称G是弱完备k-可染的。平面图G的弱完备色数是指G是弱完备k-可染的正整数k的最小值,记成χ_vef（G）。2016年,Fabrici等人猜想：每个无环且无割边的连通平面图是弱完备7-可染的。证明外平面图满足猜想,即外平面图是弱完备7-可染的。     

哈林图的弱边面染色

设G=(V,E,F)是一个无环的连通平面图,其中V表示点集,E表示边集,F表示面集.对于任意的两条相邻边e_1和e2,如果它们关联同一个面且在该面的边界上连续出现,那么称e_1和e2是面相邻的.图G是弱边面k-可染的是指存在一个映射π:EUF→{1,2,…,k},使得任意两个相关联的边和面,任意两个相邻的面,以及任意两条面相邻的边都染不同的颜色.平面图G的弱边面染色数是指G是弱边面k-可染的数k的最小值,用_(ef)(G)表示.2016年,Fabrici等人猜想:每个无环且无割边的连通平面图是弱边面5-可染的.本文我们给出此猜想的一个充分条件,即证明:哈林图是弱边面5-可染的,其中上界5是最好可能的.     

平面图3色可染的一个充分条件

Steinberg猜想既没有4-圈又没有5-圈的平面图是3色可染的. Xu, Borodin等人各自独立地证明了既没有相邻三角形又没有5-和7-圈的平面图是3 色可染的. 作为这一结果的推论, 没有4-, 5-和7-圈的平面图是3色可染的. 本文证明一个比此推论更接近Steinberg猜想的结果, 设G是一个既没有4-圈又没有5-圈的平面图, 若对每一个k∈{3, 6, 7}, G都不含(k, 7)-弦, 则G是3色可染的, 这里的(k, 7)-弦是指长度为7+k-2的圈的一条弦, 它的两个端点将圈分成两条路, 一条路的长度为6, 另一条路的长度为k-1.     

Δ(G)=5的2-连通外平面图的邻点可区别全染色

Smarandachely邻点可区别全染色是指相邻点的色集合互不包含的邻点可区别全染色，是对邻点可区别全染色条件的进一步加强。本文研究了平面图的Smarandachely邻点可区别全染色，即根据2-连通外平面图的结构特点，利用分析法、数学归纳法，刻画了最大度为5的2-连通外平面图的Smarandachely邻点可区别全色数。证明了：如果$G$是一个$\Delta （G）=5$的2-连通外平面图，则$\chi_{\rm sat}（G）\leqslant 9$。     

极大平面图的点面全色数

平面图 G(V,E,F)的点面全色数 xs(G)是使得集合 V(G)U F(G)中相邻和相关联的元素均染为不同颜色的最少颜色数.本文证明了:(1)若 G 为极大平面图,则4≤xs(G)≤6;且 xs(G)=4当且仅当 G 为点次模3-正则图.(2)若 G 为△(G)≤3的简单平面图,则 xs(G)≤6.一、引言本文限于考虑平面图 G(V,E,F),其中 V,E,F 分别为 G 的点集合,边集合和面集     

不含5-圈和相邻6-圈的平面图的全染色

图的正常k-全染色是用k种颜色给图的顶点和边同时进行染色,使得相邻或者相关联的元素(顶点或边)染不同的染色.使得图G存在正常k-全染色的最小正整数k,称为图G的全色数,用χ″(G)表示.证明了若图G是最大度△≥6且不含5-圈和相邻6-圈的平面图,则χ″(G)=△+1.     

系列平行图的边面染色

一个平面图G的边面色数xef(G)是指对G的边和面进行染色所用最少的颜色数目,并同时使得相邻或相关联的两个元素间染不同颜色.若G是一个系列平行图,也就是不含K_4的剖分作为子图的平面图,则有Xef(G)≤max{7,△(G) 1};同时如果G还是2-连通的且△(G)>6,则有Xef(G)=△.     

不包含{4,8,9}-圈的平面图是3-可染的

主要围绕Steinberg提出猜想:每个不包含4-圈和5-圈的平面图都是3-可染色的,对一些平面图类展开研究,提出要解决的问题:不包含{4,8,9}-圈的平面图是3-可染的.现从四个方面:不包含{4,8,9}-圈的平面图G的一些结构性质;不包含{4,8,9}-圈的平面图G中内部非分离6-圈的性质;不包含{4,8,9}-圈的平面图G不包含内部的6-面;f0不是一个6-面来证明结论,即不包含{4,8,9}-圈的平面图是3-可染的.     

哈林图的弱点边染色

假设e1和e2是两条相邻边,若它们关联同一个面且在该面的边界上连续出现,则称e1和e2是面相邻的.平面图G是弱点边k-可染的是指存在映射π:V (G)∪E(G)→{1,···, k},使得任意两个相邻的顶点,任意两条面相邻的边,以及任意两个相关联的顶点和边都染不同的颜色.文中利用数学归纳法证明了:哈林图(Halin graph)是弱点边5-可染的,并给出可达到上界5的例子.     

低度平面图的边面全色数

平面图G(V,E,F)的边面全色数X,(G)是使得集合E(G)∪ F(G)中相邻和相关联的元素均染为不同颜色的最少颜色数。本文提出猜想:对任何平面图G,有△(G)≤X,(G)≤△(G)+3;并对顶点度不超过3或面度均为3的平面图证明了这个猜想为真。     

不含5-圈和6-圈的平面图的(2,1)-全标号

图G的(2,1)-全标号是对图G的顶点和边的一个标号分配,使得:(1)任意两个相邻顶点标号不同;(2)任意两条相邻边标号不同;(3)任意顶点与其相关联的边标号至少相差2.两个标号的最大差值称为跨度,图G的所有(2,1)-全标号的最小跨度称为(2,1)-全标号数,记为λ_2~T(G).本文证明了如果G是一个?=p+5的平面图,且G不包含5-圈和6-圈,那么λ_2~T(G)=2?-p,p=1,2,3.     

n≤12阶(k,l)-正则极大平面图

我们知道当图的顶点数n>12时不存在正则极大平面图.相关文献提出了(k,l)-正则极大平面图的概念,并讨论了(5,6)-正则极大平面图的存在性.在相关文献中,作者分别讨论了阶n>12的(k,l)-正则极大平面图的存在条件及构造方法.本文讨论了阶n(≤12)的(k,l)-正则极大平面图的存在性,除两种情况外,本文给出了阶n(≤12)的(k,l)-正则极大平面图的存在条件及其一种构造的例子.     

无8-,9-和10-圈的平面图的3-可选择性

寻找平面图是3-或者4-可选择的充分条件是图的染色理论中一个重要研究课题,本文研究了围长至少是4的特殊平面图的选择数,通过权转移的方法证明了每个围长至少是4且不合8-圈,9-圈和10-圈的平面图是3-可选择的．     

可平面图的r-hued染色(英文)

令k0,r0是两个整数.图G的一个r-hued染色是一个正常k-染色?使得每个度为d(v)的顶点v相邻至少min{d(v),r}个不同的颜色.图G的r-hued色数是使得G存在r-hued染色的最小整数k,记为χ_r(G).文章证明了,若G为不含i-圈,4≤i≤9,的可平面图,则χ_r(G)≤r+5.这一结果意味着对于无4-9圈的可平面图,r-hued染色猜想成立.     

1-平面图及其子类的染色

如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果.     

平面图的理论与四色问题(Ⅳ)——三着色与四色问题的几何表征

§16 三色问题 三色问题之有助于四色问题者乃是极大平面图的三色问题。因为实际上四色问题只需研究那些非3-可着色的极大平面图。可喜的是这点已得到完满解决。然,一般平面图的3-可着色的判定确非那样容易。本节着重于后者。 命题16.1 极大平面图3-可着色,当且仅当所有节点的次皆偶数。 证明 由推论8.2的对偶形式和推论8.1即得。 定理16.1 任何平面图4-可着色,当且仅当非Euler极大平面图4-可着色。 证明 由于一个图是Euler图,当且仅当其节点的次皆偶。必要性是直接的。充分