平面三次图哈米尔顿性的一个充要条件

本文证明平面三次图Dg有哈米尔顿圈的充分必要条件是与之对偶的极大平面图g有树树型四着色．即Dg的对偶极大平面图g有四着色C，该四着色的某组对偶二色子图Gk的两个分支都是树．据此得到求出图Dg全部哈米尔顿圈的算法，该方法已经成功处理了批量例图．     

Thomassen与曲面嵌入图的着色

曲面嵌入图的着色的研究起源于Heawood地图着色定理.本文在对原始文献进行研究的基础上,论述Thomassen在三色定理与列表着色、曲面嵌入图的着色、色多项式和着色的数目等方面的工作.他的研究受到了Mohar,Thomas和Hutchinson等许多数学家的关注.     

Heawood图的一对对偶树的分解和4-着色

阐明了任意平图的4-着色的主要思路,给出了对偶树的定义。对偶图中的一对对偶树与对偶图的Hamilton路径相互依存,提出了任意平图的4-着色的方法步骤。得到利用上述方法得到的一对对偶树及具有的性质。介绍了Heawood图的由来和基本特点、Heawood图的4-着色的2种方法步骤,通过对偶图的2个区域的划分,实施了Heawood图的4-着色,借助于Heawood图的对偶图的Hamilton路径的分解构造了2棵对偶树。借助于此方法所得的Heawood图的25个顶点的4-着色方案达到236个,从而使Kempe的4-cc猜想"证明"中的漏洞得到弥补。     

平面三次图中的二元哈米顿圈

本文定义了平面三次图中的二元哈米顿圈,并证明了:平面三次图Dg有二元哈米顿圈,充分必要的是,与之对偶的极大平面图g有树-圈-树型四着色,更具体地说是,与图Dg对偶的极大平面图g有四着色C,该四着色的某组对偶二色子图:Gk=RUS,其中R连通并且仅仅包含一个圈;S有两个分支,并且都是树.据此,得到求出图Dg全部二元哈米顿圈的算法.该方法已经成功处理了批量例图.     

毛虫树可均匀k-着色的一个充分条件

用k种颜色给一个图的顶点正常着色,即使相邻的顶点不同色,若各色类的基数至多差一,则称该图是可均匀k-着色的.基于均匀着色的理论本文得到了毛虫树可均匀k-着色的一个充分条件.     

顶点着色的若干结果

色数理论研究是图论研究的一个重要方面．在引入了最优顶点着色概念的基础上，获得了图的色数的系列上界，刻画了图的色数与图的特征根之间的关系，即用图的特征根来估计图的色数的上下界。     

一类稠密图的色唯一性

用Pn表示有n个顶点的路.Dn表示把K3的一个顶点与Pn-2的一个一度顶点重迭后得到的图.Fn表示把K3的一个顶点与Dn-2的一度点重迭后得到的图.用伴随多项式来讨论图的着色唯一性.得到Fn的补图色唯一的充要条件是n≠17.彻底解决了这类稠密图的色性.     

毛虫树可均匀κ-着色的一个充分条件

用κ种颜色给一个图的顶点正常着色。即使相邻的顶点不同色，若各色类的基数至多差一。则称该图是可均匀κ-着色的。基于均匀着色的理论本文得到了毛虫树可均匀κ-着色的一个充分条件。     

极大平面图中二色树子图的一个必要条件

极大平面图G=(V,E)中的一个二色树子图T=(Vt,Et),其Vt在G中导出子图为树,并且图G存在至少一个四着色C,使T是该四着色一个二色子图的一个连通支.本文证明了Vt的点次和为偶数是它成为二色树子图的必要条件.     

基于kn连接关系的图的着色问题与"折叠法"

引入了一类基于连接关系的图,并结合“折叠法”对该类图的着色问题与四色猜想进行了研究,给出了四色猜想的一个必要条件和一个等价命题的证明．最后提出了相关的猜想．     

Ramsey数R4（6）的新下界

推广Mathon的方法，并对4色完全图K929进行研究，得到Ramsey数R4(6)的新下界：R4(6)≥3721．     

围长为4的平面图不总是3－可选色

针对ＫｒａｔｏｃｈｖｉｌＪ和ＴｕｚａＺ（１９９４）提出的问题：是否每一个国长为４的平面图总可以３－可选色（３－ｃｈｏｏｓａｂｌｅ）？用组合技巧构造了一个反例，从而证明了围长为４的平面图并不一定是３－可选色的，否定了每一个３－可着色的图一定是３－可选色的这个论断．     

两类图的边色数

设G是连通循环图.本文讨论两个与循环图有关的图类的边着色问题,得到了下列结论:①如G是奇素数幂阶循环图,则对G的任意点v,G-v是第一类的;②如G是奇数阶循环图,则G的线图L(G)是1-可因子化的,当且仅当G的边数为偶数。     

控制圆点临界图的若干性质

对于图G,如果收缩任意一条边,它的控制数下降,则称图G是圆点临界图.如果粘贴图G中任意两个顶点,它的控制数下降,则称图G是全圆点临界图.证明了对于k-正则图,当k为奇数时不存在2-全圆点临界图;当k为偶数时当且仅当此图为k+2阶图时其为2-全圆点临界图.还对是否存在不含临界点的k-全圆点临界图(k≥4)进行了研究,并得出结论:存在不含临界点的4-全圆点临界图和5-全圆点临界图.     

K-优美图与优美图Gk-1的优美性研究

对k-优美图n,Km,n与任意一个有k-1条边的优美图Gk-1的优美关系进行了研究.证明了:当n为奇数时,图n∪Gk-1是优美图;当n为偶数时,粘接图〈n,Gk-1〉是优美图.还证明了粘接图〈Km,n,Gk-1〉是优美图.     

广义Petersen图GP(n,k)的着色

本文研究广义Petersen图GP(n,k)的点着色、边着色和点-边全着色,得到广义Petersen图GP(n,2)的点色数、边色数和全色数,同时还得到当n为偶数,k为奇数时,该广义Petersen图GP(n,k)满足点-边全着色猜想等结论.     

关于3-连通图的一个猜测的反例

1978年,Dirac 给出了从2-连通图 G 中的最长路判断 G 的周长下界的一个定理.在1983年的西安图论讲习班上,朱永津提出了一个与 Difac 定理形式相似但条件较强结论也较强的猜测.通过发现一个反例,本文得到了这一猜测的否定解答。     

冠状系统R-旋转图连通的充要条件

六角系统的R-旋转图是1棵有向根树,但冠状系统的R-旋转图是一个有向森林.其底图不一定连通.如果冠状系统是基本的,已经证明其R-旋转图至少包含2棵有向根树.利用有向根树问的一种乘法运算,证明了一个冠状系统的R-旋转图为1棵有向根树当且仅当该冠状系统的每个基本分支都是六角系统.     

关于奇优美图及奇强协调图的一点注记

讨论了奇优美图及奇强协调图的必要条件,证明了完全偶图Km,n是奇优美图及奇强协调图。