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

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

双外平面图的边面染色

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

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

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

不含相邻4-圈的1-平面图边染色

利用权转移方法证明最大度为9且不含相邻4-圈的1-平面图是9-边可染的．     

最大度为8不含相邻4-圈的1-平面图边色数

利用权转移方法证明了最大度为8且不含相邻4-圈的1-平面图是8-边可染的。     

基于平面图的改进Dijkstra算法研究

针对在平面图应用条件下，对应用Dijkstra算法进行最短路径搜索的设计方法和运算过程进行分析，从应用的角度，改进Dijkstra算法，设计一种新的数据存储结构，并建立简洁的估价函数，使基于平面图的动态最短路径规划算法在时间复杂性和空间复杂性均达到线性．     

开外平面图的边面全色数

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

一类平面图的强边着色

图G的强边着色是正常边着色且任何长为3的路的边不着双色.图G的强边色数是G的所有强边着色中使用色数的最小者,记为χ′s(G).证明了如果图G是平面图且满足g(G)≥14,则χ′s(G)≤|(5Δ2-2Δ+1)/4|,其中g(G)表示图G的围长.     

关于平面图的边面全着色

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

基于平面图的最短路径算法的研究

研究平面图特殊应用条件下最短路径搜索算法的时间复杂度和空间复杂度。从应用的角度,设计一种新的数据存储结构,改进最短路径搜索算法,并建立一个简捷的估价函数,使基于平面图的动态路径规划算法在时间复杂性和空间复杂性上均达到了线性,为进一步解决这一领域内的网络综合分析打下了基础。     

外平面图的边面 List 染色

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

关于互补平面图的Akiyama-Harary问题

本文回答了同由J. Akiyama与F. Harary提出的关于互补平面图偶的个数的问题。证明了恰好有1495对互补平面图偶。     

第一类平面图的一个充分条件

对于最大度为5的平面图,既有第一类,也有第二类.运用Discharge方法以及临界图的一些重要性质证明了:每个最大度为5且不含相交三角形的简单平面图的边色数等于5,即这样的平面图是第一类的.因此,给出了最大度为5的平面图分类的一个特征刻画.     

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

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

平面图无圈边着色的一个结果

图G的无圈边着色是指图G的一个正常边着色且不含双色的圈.图G的无圈边色数是指图G的无圈边着色中所用色数的最小者,用x’a(G)表示;证明了如果G是一个D中的顶点不与3-面相关联,3-顶点不与D中的顶点相邻且Δ(G)≥6的平面图,则x’a(G)≤Δ(G)+1。     

NIC-平面图中轻风筝的存在性

将K_1,3任意两点连接起来所形成的图形称为风筝.设H是一个连通图,■是一个图类,如果对任意的■包含一个子图K,K同构于图H,且满足■那么称H为■的轻子图.如果H是一个风筝,就称H为轻风筝.利用权转移方法研究了NIC-平面图中轻风筝的存在性,证明了每个最小度至少为5并且最小边度至少为11的NIC-平面图含有一个最大度至多为29的风筝.     

△≥r—2的极大外平面图的4染色

从最大度的角度讨论极大外平面图的染色,证明了以ｒ个顶点在圈Ｑｒ为标定界环的最大度△≥ｒ－２的任意两个极大外平肌图都有公共４染色。     

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

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

外平面图的一个结构定理

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

一些平面图的无圈边染色

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