关于图的边染色方面的一些结果

改进了一些边染色临界图的边数的下界。同时证明了：对没有４－圈或任何两个３－面都不同时关联于一个点的平面图，关于边染色的平面图猜想成立。     

最大度为6且不含5圈或6圈的平面图可8全染色

G,G的k 全染色是指用k种颜色给G的点和边进行染色,使G的任意邻接点或邻接边均染不同的颜色,且G的任一点与该点的任一关联边均染不同的颜色．证明了最大度为6且不含5 圈或6 圈的平面图是可8 全染色的．     

Halin图的边列表染色

图的染色是图论的重要研究内容之一．平面图染色是其中的一个主要方面．有各种各样的染色方式，近来，又出现了列表染色［１］．定义１称图Ｇ是ｋ－边可选择的．如果任给ｅ∈Ｅ（Ｇ），和边ｅ的任给颜色集Ｌ（ｅ），｜Ｌ（ｅ）｜＝ｔ，都可以选一种颜色σ（ｅ）∈Ｌ（ｅ）...     

p_1-类图的双约束边色数

双约束边染色是指对平面图G的边进行染色,使得相邻的边染不同的颜色且在同一个面上的边也有不同的颜色.图G的双约束边色数χe/vf(G)是指对图G进行双约束边染色所需要的最少的颜色数,各种平面图的双约束边色数的上界是研究双约束边染色的焦点问题.证明了对于高度平面图中的p1-类图,恒有χe/vf(G)≤Δ(G)+1成立,其中Δ(G)为图G的最大度.     

平面图的全染色

给定一个图G,G的全k染色是指至多用k种颜色,对G的顶点和边同时进行染色,使得相邻的两个元素染不同颜色。对△(G)8,且每点至多关联2个3-圈的平面图,有τ(G)=△(G)+1。     

Series-Parallel图的全选择数与全色数

对2-连通Series-Parallel图G，证明了当△（G）≥4时，其全选择数等于△（G） 1；在△（G）≥3时，其全色数等于△（G） 1；对△（G）≠时，其边选择数等于其边色数（即列表染色猜想）。由于外平面图是特殊的Series-Parallel图，本文包含了外平面图的相应染色结论。     

不含相交三角形的平面图的无圈边色数的新上界

图G的无圈边染色是图论染色的重要研究对象,为得到平面图的无圈边色数的上界,利用差值转移方法和平面图的结构性质,证得了不含相交三角形的平面图的无圈边色数不超过Δ(G)+6。     

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

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

几类特殊平面图的圈包装问题

给定一个无向连通图G，圈包装问题就是求G的边不相交圈的最大数目．此问题在一般图下是APX困难问题，在平面图下是NP困难问题．主要证明了在几类特殊的平面图下多项式时间可得到最优解．主要考虑外平面图，系列平行图和平面欧拉图这三类特殊的平面图．     

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

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

平面图与对偶原理

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

含有两个分离三角形的极大平图有一个Hamilton路

一个图若包含Hamilton圈，则这个图是Hamilton图．Whitney已经证明了没有分离三角形的极大平图是Hamilton图．一个三角形若删去其顶点后使图不连通，则这个三角形称为分离三角形。Chuiyuan Chen证明了仅含有一个分离三角形的极大平图仍然是Hamilton图，我们将证明含有两个分离三角形的极大平图有一个Hamilton路。     

极大平面图的导出四正则图的三着色

本文给出了极大平面图的导出四正则图的两种构造方式、等价性及性质,证明了导出四正则图的三着色与原极大平面图四着色的一一对应关系,并且找出了导出四正则图的三种颜色与原极大平面图四着色的三组对偶二色子图之间的关系.     

一些平面图的无圈边染色

主要研究了平面图的无圈边染色问题。证明了对平面图G,如果G不包含3,5圈,且G中任意两个4-圈都不共边,则无圈边染色猜想成立;并且,如果G不含3-圈,且任意两个4-圈不共点,则G的无圈边染色数不大于Δ(G)+3。     

最大度是4的可平面图的边染色

对于最大度是Δ的可平面图G,如果χ′（G）=Δ称G为第一类图,如果χ′（G）=Δ＋1称G为第二类图,χ′（G）表示G的边染色数.1965年,Vizing举例说明,最大度是4的平面图中不仅有第一类图,也有第二类图.论文运用Discharge方法及临界图的重要性质证明：最大度是4,不含5圈和6圈,且任意两个相交面的度不相同的可平面图是第一类图.     

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

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

最大度为5且不含有4-圈的平面图的边色数

对于最大度为5的平面图,既有第一类的,也有第二类的.运用D ischarge方法证明了最大度为5且不含有4-圈的平面图的边色数等于5,即这样的平面图是第一类的,并给出了最大度为5的平面图分类的一个特征刻画.     

最大度是5的可平面图的边染色

对于最大度是Δ的可平面图G,如果χ′(G)=Δ,称G为第一类图;如果χ′(G)=Δ+1,称G为第二类图.χ′(G)表示G的边染色数.1965年,Vizing举例说明Δ=5的可平面图中既有第一类图,也有第二类图.作者运用Discharge方法证明最大度是5且不包含有弦的4-圈和有弦的5-圈,或不包含有弦的4-圈和有弦的6-圈的可平面图是第一类图.     

对偶图中的H圈与平图的4着色

阐明了对偶图中的H圈与平图的2棵对偶树的相互依存关系,阐述了平图的4着色与2棵对偶树之间的相互依存关系。平图的顶点4着色以及2棵对偶树的分解决定了对偶图中的H圈,对偶图中的H圈也决定了平图的顶点4着色及2棵对偶树的分解。平图H圈决定了对偶图的2棵对偶树的分解及顶点4着色,对偶图的2棵对偶树的分解及对偶图的顶点4着色决定了平图的H圈的分解。2棵对偶树的2着色等价于平图的顶点4着色,内区与外区的分界线恰好是H圈。提出了多面体平图的H圈的构造步骤和多面体平图的顶点4着色步骤。介绍了12面体平图中30个H圈的构造,对偶图中对偶树的分解、以及对偶树的4着色。解决了任意平图中的H圈的分解方法和计数方法,为解决任意平图中的生成树的构造和计数问题奠定了基础。