不含特殊短圈平面图的无圈边染色

无圈边染色是指图G的一个正常边染色,使其不产生双色圈.研究了不含特殊短圈平面图的无圈边染色问题,证明了：如果平面图G不含4到8-圈,那么G的无圈边染色数不大于Δ（G）＋1.     

特殊平面图的线性二荫度

线性k-森林是指一个图G，它的每个连通分支是长至多为k的路．图G的线性k-荫度是指使得G可以边划分成m个线性k-森林的最小整数m，用lak（G）表示．本文探讨特殊平面图的线性二荫度，得到的结论有：1）每个3-圈不重边的平面图G，有la2（G）≤[△（G）／2]＋10；2）每个3-圈不重点的平面图G，有la2（G）≤[△（G）／2]＋7；3）每点至多关联[△（G）／2]个3-面的平面图G，有la2（G）≤[△（G）／2]＋10．     

不含3圈的平面图的无圈边染色

图的无圈边染色是图的染色理论中的一个重要问题,2001年,Alon等猜想任意简单图G的无圈边色数都不超过△（G）＋2,其中△（G）为图G的最大顶点度。为了研究该猜想对平面图是否成立,利用差值转移方法,证明了不包含三角形的平面图G的无圈边色数不超过△（G）＋3．     

1-树与外平面图的无圈边着色

设f是图G的一个正常边着色，若在f下G中没有2-色圈，则称f是图G的一个无圈边着色，其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图，无圈边色数不超过其最大度加2。本文证明了该猜想对1-树与外平面图成立，且它们的色数均不超过最大度加1。     

外部平面图的平方图的染色

图G的平方图，记作G^2，是一个以原图的顶点集为顶点集，若原图中两点的距离不大于2则连以边所成的图．本文确定了圈的平方图的色数．对于外部平面图，得到以下结论：设G是一个最大度为△(G)的简单连通外部平面图，G≠C5．则x(G^2)≤△(G) 2．     

关于平面图点荫度的一点改进

一个非平凡图G的点荫度a(G)是一个最小图顶点划分数使得每一个划分集的导出子图是一个森林.近年来对点荫度的研究成为图论的一个焦点并且关于这个问题有更深一步的发展,例如,随机图的点荫度以分式点荫度等.得到一个关于平面图的点荫度的一个上界;如果平面图G是没有3-圈,或是没有4-圈,或是没有5-圈,那么G的点荫度不超过2.研究的起因是一个著名的猜想:任何3-可着色的平面图的点荫度不超过2.四色定理是图论中最著名的一个定理,伴随产生了一个问题,那就是什么样的平面图是3-可着色的.不幸,这是一个难问题,Garev等人证明了判定一个平面图是否3-可着的即使在一个点不超过4的条件下仍然是NP-难问题.因此这个猜想是一个不易解决的,人们开始在一些特殊图上进行验证这个猜想是否正确.我们知道一个著名的定理:不含3-圈的平面图是3-可着色的.结合结果,给出猜想的一个正面的肯定.Havel给出两个反例,如果平面图含有4-圈或有5-圈是不可3-可着色的,因此4-圈和5-圈在证明平面图是3-可着色时必须排除.不过在结论中,如果平面图不含有4-圈或不含有5-圈,那么它的点荫度不超过2.从而可以看出猜想的条件还是很强的.同时我们的结果也拓宽了张忠辅等人的结果:外平图的点荫度不超过2.     

5~--圈和5~--圈不交的平面图的injective-列表染色

通过构造一个(Δ+6)-临界图,运用权转移的方法证明了:对于5~--圈和5~--圈不交且Δ(G)≥18的平面图G,有χ■(G)≤Δ(G)+6.所得结果研究了平面图G在短圈不交的限制条件下的injective-列表染色的问题.     

一圈谐振平面图的构造

如果连通图G是一圈谐振平面图,那么(G+P)(x,y)未必是一圈谐振平面图。从苯环型碳氢化合物的碳原子结构图——六角系统出发,在K圈谐振图的基础上引出了一圈谐振可约链的概念及其相关结论,并给出了确定(G+P)(x,y)是一圈谐振平面图的条件。     

不含4圈的平面图的无圈边染色

如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数。利用已有的关于平面图的结构性质,证明了不含4圈的2-连通平面图的无圈边色数不超过Δ(G)+11。     

不含相交三角形和4圈的平面图的无圈边染色

如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数。利用差值转移方法并结合平面图的结构性质,证明了不含相交三角形和4圈的平面图的无圈边色数不超过△(G)+6。     

不含三角形的平面图的无圈边染色

图的无圈边染色是图的染色理论中的一个重要问题.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度.为了深入研究该猜想对平面图是否成立,利用差值转移方法并结合最小反例图的一些结构性质,证明了:不包含三角形的平面图G,如果其最大顶点度不小于6,则其无圈边色数不超过Δ(G)+3.     

不含3,4圈的平面图的无圈边染色的一个结果

利用差值转移方法研究了不含3圈,4圈的平面图的无圈边染色,证得了它们的无圈边色数不超过Δ(G)+2。     

平面图选择控制集问题的复杂性分析及算法设计

研究平面图的选择控制集问题．通过PX3C(planar exact cover by 3-sets)到平面图控制集的变换，证明了平面图的控制集问题是NP完全的，从而得到平面图的选择控制集问题的NP完全性．同时提出了一个基于遗传算法的求平面赋权图的选择控制集的近似算法．     

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

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

平面图与对偶原理

该文利用对偶原理创造性地解决了平面图、连通图及对偶图之间的相互关系问题,纠正了长期以来对于平面图及其同构的错误认识,指出平面图必为连通图,平面图本质上是画在同一平面上的顶点、边、面均不相交的连通图。两个平面图的同构指这两个平面图的顶点、边、面之间均有一一对应关系。面是平面图区别于非平面图的本质特征。同构的平面图的对偶图必同构,事实上,平面图的对偶图是唯一的。任意一个平面图都伴有一个隐图,而该隐图实质上是该平面图的对偶图,该隐图可(根据对偶原理)通过D—过程画出。平面图与其对偶图互为对偶。显平面图与其隐对偶图合称为相伴对偶图。     

P3——支配图哈密尔顿性的一个充分条件

在文献[4]中作为半无爪图的一个超类,作者引进P3-支配图,并研究了这类图一些性质。设G是2-连通的P3-支配图,我们证明了G是哈密尔顿的一个充分条件局部连通型条件。     

完全多部图和笛卡儿积图的线性点荫度

图的线性点荫度是对它的顶点进行染色所用的最少颜色数,同时使得染同一种颜色的点集所导出的子图,它的每个分支均为路．本文完全确定了完全多部图的线性点荫度,给出了笛卡儿积图的线性点荫度的一个上界,得到了一些特殊图（ 如路,圈和完全图） 的笛卡儿积图的线性点荫度．     

P3-支配图哈密尔顿性的两个充分条件

在文献[4]中作者引进P3-支配图,并研究了这类图的一些性质.设G是2-连通的P3-支配图,证明了G是哈密尔顿的两个充分条件fan型条件和禁止子图型条件.     

程序流图的道路问题

本文研究了既含简单的不可归约流图,又含不具互优反向点的可归约流图的单性流图类,并考虑了把在单性流图类的简单道路集上的分析问题,代之以在它的无圈子图类的道路集上的分析的方法和形式。