临界极大外平面图

给出了临界极大外平面图以及最大度临界极大外平面图的定义，并讨论了它们的性质，为研究极大外平面图的四染色提供了一种新方法。     

外平面图结构性质的若干问题

研究了外平面图的结构性质，得到了外平面图的边数可达的上界，并且推得外平面图均为第Ⅰ类图的结论     

关于平面图的边面全着色

定义了平面图的边面全色数，提出了相应的猜想，证明了无割点外平面图的最大度不少于７时，其边面全色数等于其最大度。     

平面图的完备List染色

设Ｇ是２－连简单平面图，ｘ＾ｖｅｒ（Ｇ）为Ｇ的完备Ｌｉｓｔ和选择数。本文证明若Ｇ为最大度△（Ｇ）≥７的２－连通外平面图，则ｘ１＾ｖｅｒ（Ｇ）＝△（Ｇ）＋１     

极大外平面图谱半径的上界

每个点都在图的一个面的边界上的平面图叫外平面图,具有最大边数的外平面图叫极大外平面图.首先给出了一类极大外平面图的特征多项式的表达式,由此给出了对任意n≥4都成立的极大外平面图谱半径的一个上界,并证明了当图的点数增大时,这个上界与谱半径是等价的无穷大量.     

开外平面图的边面全色数

一个无割点的外平面图称为开外平面图，如果它的每一个内面的边界至少含有一条外边。本文证明了：若Ｇ为开外平面图，则（ｉ）当△（Ｇ）＝３时，ｘ２３（Ｇ）＝４，当△（Ｇ）≥５时，ｘ２３（Ｇ）＝△（Ｇ）；（ｉｉ）当△（Ｇ）＝２，４时，４≤ｘ２３（Ｇ）≤５，其中ｘ２３（Ｇ）为平面图Ｇ的边面全色数，△（Ｇ）是Ｇ的点最大度。     

两类平面图的指数集

完全确定了极大可平面图与极大外可平面图的指数集。     

2-外平面图的无圈边色数

研究了2-外平面图的无圈边染色问题.运用删点变换,得到了2-外平面图的结构性质;继而,运用数学归纳法,得到了图的一个无圈(Δ(G)+3)-边染色,即得到:若G是一个2-外平面图,则a’(G)≤Δ(G)+3.     

n阶极大外平面图的构造法

图的同构的判定是图论研究中的重要课题之一,非同构的极大外平面图的计数问题尚未解决.提出一种判定图同构的方法,其原理是赋予每个无标号极大外平面图一个n×(n-3)阶0-1矩阵,证明了矩阵与极大外平面图一一对应,矩阵相同的图彼此同构.构造所有可能的n阶极大外平面图,并用上述方法除去其中同构者,所有n阶无标号极大外平面图被不重不漏地构造出来,同时得到其总个数,解决了有关极大外平面图同构与计数问题.     

2-外平面图的L（2，1）-标号数

一个平面图被称为 2-外平面图,如果它能嵌入平面使得所有顶点出现在至多2个面的边界上.主要研究了2-外平面图的L(2,1)-标号,得到:若图G是一个2-外平面图,则λ(G)≤Δ(G)+12,其中Δ(G)表示G的最大度.     

外平面图的边面 List 染色

设Ｇ是无割点平面图，ｘｅｆｌ（Ｇ）为Ｇ的边面Ｌｉｓｔ选择数。本文证明了若Ｇ为最大度Δ（Ｇ）≥６的无割点外平面图，则ｘｅｆｌ（Ｇ）＝Δ（Ｇ）。     

关于高度极大外平面图的4染色

从最大度的角度讨论两大极大外平面图的公共４染色，证明了当Ｇ是以ｒ个顶点的圈Ｑｒ为标定界环的极大外平面图且△（Ｇ）≥ｒ－２，Ｇ′是以Ｑｒ为标定界环的任一极大外平面图时，Ｇ和Ｇ′有公共４染色，从而证明了四色定理的等价例题在给定条件下成立。     

外平面图的一个结构定理

给出了外平面图的拟对偶图的定义,并利用拟对偶图的性质证明了外平面图的结构定理。     

外平面图的结构性质及在边着色上的应用

给出并证明了外平面图的两个结构性质：(1)△≥5时，存在一个最小面，至多关联于一个△度点；(2)△=4且每个最小面均关联两个4度点时．存在闭内部面。作为性质的应用，更简捷的证明了非奇圈的外平面图为第一类图。     

双外平面图的边面染色

双外平面图是一个平面图，它可以嵌入到平面上并使得它的顶点出现在两个面的边界上．证明了对于最大度至少是6的双外平面图，有Xef(G)≤△(G) 1，其中△(G)是G的最大度．     

一个求外平面图最小反馈点集的多项式时间算法

如果从一个图中去掉某些顶点后得到的导出子图是无圈图，则所去的那些顶点组成的集合就是原图的反馈点集。本文讨论外平面图的反馈点集并给出了一个求外平面图最小反馈点集的多项式时间算法。     

关于完备色数（II）

平面图Ｇ（Ｖ，Ｅ，Ｆ）的完备色数χｃ（Ｇ）是使得集合Ｖ（Ｇ）∪Ｅ（Ｇ）∪Ｆ（Ｇ）中的相邻点，相邻边、相邻面、相关联的点边、相关联的点面及相关联的边面均染为不同颜色的最少颜色数。一个无割点的外平面称为开外平面图。如果它的每一个内面的边界至少含一条外边。本文证明了：若Ｇ为开外平面图且其顶点最大度△（Ｇ）≥６，则χｃ（Ｃ）＝△（Ｇ）＋１。     

关于图的线性点荫度

Ｂｒｏｅｒｅ和Ｍｙｎｈａｒｄｔ等人猜想：任何平面图Ｇ的线性点荫度ｌａ（Ｇ）不超过３。本文证明了这个猜想，并证明了外平面图的线性点荫度ｌａ（Ｇ）不大于２。     

极大平面图与外可平面图的同构不动边

图Ｇ的一条边ｅ称为Ｇ的同构不动边，如果Ｇ－ｅ＋ｅ≌Ｇ当且仅当ｅ′＝ｅ，若ｅ＝ｕｖ是Ｇ的同构不动边，则对Ｇ－ｅ的任一自同构映射π都有π（ｕ，ｖ）＝（ｕ，ｖ）文中证明了，除Ｋ３Ｖ（Ｋ１＋Ｋ１）外的极大平面图和除Ｐ２ＶＫ１，Ｐ３ＶＫ１外的２－连通外可平面图都含有同的构不动边。     

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

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