On the (Δ + 2)-Total-Colorability of Planar Graphs with 7-Cycles Containing at Most Two Chords

The Total Coloring Conjecture (TCC) proposes that every simple graph G is (Δ + 2)-totally-colorable, where Δ is the maximum degree of G. For planar graph, TCC is open only in case Δ = 6. In this paper, we prove that TCC holds for planar graph with Δ = 6 and every 7-cycle contains at most two chords.

Total colorings of planar graphs with maximum degree at least 8

Planar graphs with maximum degree Δ 8 and without 5- or 6-cycles with chords are proved to be (Δ + 1)-totally-colorable.

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

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

平面图的无圈边染色

一个图G的无圈边染色是一个正常的边染色,使得不产生双色圈.Fiamˇcik和Alon等分别提出了著名的无圈边色数猜想:每一个简单图G是无圈边(Δ+2)可染的,其中Δ是G的最大度.证明了对于不含3圈和5圈相邻的平面图猜想成立.

“四色问题”研究

通过极大平面图的结构研究，提出了构造极大平面图的三种方法，即“加点法”、“删点法”与“任意法”．建立了一个理论系统，包括１１个定义，１２个命题及７个定理．采用“平行归纳法”证明了极大平面图可四着色，从而证明了“四色猜想”

高度平面图的L(p,q)-标号

研究高度平面图G的L(p,q)-标号问题,证明了高度平面图h1-图的L(p,q)-标号数满足:λ(G;p,q)(2q-1)Δ+6(p-q);h2-图的L(p,q)-标号数满足:λ(G;p,q)(2q-1)Δ+8p-6q-1.对于L(2,1)标号问题Griggs和Yeh有一著名猜想:对最大度为Δ的任意图有λ(G)Δ2.此猜想对高度平面图是正确的.

最大度是6的平面图是第一类图的一个充分条件

用χ′(G)表示G的边染色数.对于最大度是Δ的可平面图G,如果χ′(G)=Δ,称G为第一类图;如果χ′(G)=Δ+1,称G为第二类图.运用Discharge方法证明:最大度是6且不含7圈的可平面图G是第一类图.

不含4-和5-圈的平面图的均匀染色

一个图G是均匀k-可染的,如果G有一个k-染色(V1,V2,…,Vk),使得对任何i,j∈{1,2,…,k}有||Vi|-|Vj||≤1.应用细致的结构分析和经典的discharging方法证明了:最大度5≤Δ≤6且没有4-,5-圈的平面图是均匀Δ-可染的.

围长至少为5的平面图的线性染色

如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用1c(G)表示,是指G的所有线性染色中所用的最少颜色的个数.本文证明了对于每一个最大度为△(G)且围长至少为5的平面图G有1c(G)≤[△(G)/2]+5,并且当△(G)(?){7,8,…,14}时,1c(G)≤[△(G)/2]+4.

最大度是4的可平面图是第一类图的充分条件

运用Discharge方法证明:最大度是4,且满足下列条件之一的可平面图G是第一类的.(1)G中不含长度为4至9的圈;(2)G中不含4-圈和5-圈,且任意两个3-面不关联于同一个顶点;(3)G中不含长度在5和8之间的圈,且任意两个3-圈,任意两个4-圈不关联于同一个顶点;(4)围长不小于4,G中不含有弦的8-圈,且任意两个4-面不关联于同一个顶点.

△(G)=4的平面连通图的存在性及其分布区域

本文证明了两个关于最大度为4的平面连通图的存在性定理,并确定了此图类的三种类型的分布区域。

最大度是6不含相邻k-圈的可平面图的边染色

运用Discharge方法和临界图性质证明了,最大度是6且任意两个长度至多是6的k-圈不相邻的可平面图是第一类图.

不含3-圈平面图的线性染色

运用Discharging方法,研究了平面图的线性染色问题,证明了一个没有3-圈的平面图G的线性色数lc(G)≤「3Δ(G)」+2,其中Δ(G)表示G的最大度.

最大度是6且不含有弦的小圈的可平面图的边染色

对于最大度是Δ的可平面图G,如果χ'(G)=Δ,称G为第一类图;如果χ'(G)=Δ+1,称G为第二类图,χ'(G)表示G的边染色数.1965年,Vizing证明了任何一个Δ≥8的可平面图均是第一类图,并猜想Δ=6的可平面图也是第一类图.本文运用Discharge方法证明了最大度是6,且不含有弦的k-圈的可平面图是第一类图(4≤k≤7).

最大度为11的平面图的列表全染色

在著名的列表全染色猜想(LTCC)仍未完全证明的情况下,证明了对于最大度为11且不含相邻三角形的平面图是12全可选择的,从而进一步支持了列表全染色猜想.

Δ≥r-2的极大外平面图的4染色

从最大度的角度讨论极大外平面图的染色．证明了以ｒ个顶点的圈Ｑｒ为标定界环的最大度Δ≥ｒ－２的任意两个极大外平面图都有公共４染色．

12阶的(4,8)-正则极大平面图的不存在性

当图的顶点数n>12时,不存在正则极大平面图。S.Karimi et.al.提出了(r,k)-正则极大平面图的概念,并讨论了(5,6)-正则极大平面图的存在性。作者曾讨论了阶n>12的(k,l)-正则极大平面图的存在条件及构造方法,研究并讨论了阶n(n>12)的(k,l)-正则极大平面图的存在性及其构造,对于剩余的两种情况,同时提出了两个猜想。本文在此基础上又证明了其中一个猜想的正确性——不存在12阶的(4,8)-正则极大平面图。

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

在S.Karimis和Dragan Stevanovic研究的基础上,研究并得出了(k,l)-正则极大平面图存在的必要条件。并对存在的(k,l)-正则极大平面图进行了构造。不仅彻底解决了S.Karimis提出的问题,而且就是否存在对应阶n>12的(k,l)-正则极大平面图研究和证明,并得出当阶n>13时仅存在(3,6)、(4,6)、(5,6)-正则极大平面图,同时给出了对应的(k,l)-正则极大平面图的一种构造方法。

最大度为6的平面图是13-线性可染的

图G的线性色数lc(G)是指G的所有线性染色中所用的最少颜色的个数.运用Discharging方法,研究了平面图的线性色数问题,证明了最大度为6的平面图是13-线性可染的.

最大度为5的可平面图是第一类的充分条件

最大度是5的可平面图,既有第一类,也有第二类。该文运用Discharge方法以及临界图的一些重要性质证明,每个最大度为5且不含三圈或不含四圈或不含五圈的简单平面图的边色数等于5,即这样的平面图是第一类的。文中还给出了最大度为5的平面图分类的一个特征刻画。