不含C8和相邻三角形的连通平面图的BB染色

证明了如果图G是一个连通的平面图且不包含C8和相邻三角形,那么肯定存在一棵G的生成树T使得χb(G,T)≤4。     

三次图的结构特征

通过对三次图结构的研究给出了两个主要结论：（１）对连通度μ（Ｇ）＝０，１，２，３，分别给出点数Ｐ＝｜Ｖ（Ｇ）｜的可达到的下界；（２）２—连通图Ｇ，存在２—连通三次图Ｇ′，Ｇ′可收缩到Ｇ。     

Heawood反例图的全部四着色

本文首次报告了Heawood反例图的全部四着色.它可以用一个树林来描述.树林的每个分支是一棵四着色树.四着色树是一个根树.根节点Cr是Heawood反例图的一个四着色.根树其它节点都是经过一个或多个二色变换从Cr变来的.Heawood反例图有37个四着色树.其中有35个偶四色树(包括24个是仅有根结点的退化型四色树),2个奇四色树.偶四着色总计112,奇四着色总计144,全部四着色总共256个.这些结果都是用Maple编程得到的.     

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

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

基于AutoCAD的公路及铁路线路平面图出图方法

在分析AutoCAD二维和三维图形功能的基础上,提出了基于AutoCAD现有图形功能的公路路线平面图分幅出图方法以及铁路线路平面图连续出图方法,可简单而方便地由打印机或绘图机输出符合要求的平面图.     

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

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

一类外平面图的有界染色

图G的k-有界染色是图G的一个最多有k个顶点染同一种颜色的顶点染色．图G的k-有界染色数χk(G)是指对图G进行k-有界染色所用的最少颜色数．讨论一类外平面图的k-有界染色，给出能在多项式时间内确定其k-有界染色数的一些充分条件．     

平面图与对偶原理

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

d(f)=i的平面图

Ｓａｃｈｓ,Ｋｏｚｙｓｅｖ和Ｇｒｉｈｂｅｒｙ指出平面图具有Ｈａｍｉｌｔｏｎ图的一个必要条件是ｎｉ＝３（ｉ－２）ｉ＝ｎｉ＝３（ｉ－２）′ｉ＝ｎ－２,其中ｉ和′ｉ分别为Ｈａｍｉｌｔｏｎ圈内、外度为ｉ的面数。本文探讨面的度相等的平面图及面并成顶点在边界上的连通区域的面数．