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

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

外可平面图的圈基结构

在ew（G）≥5的条件下。研究在平面和射影平面上2-连通的外可平面图的圈基结构,给出在这两种平面上嵌入的最小圈基,结果表明,平面上的最小圈基仅与面圈有关,射影平面上的最小圈基不仅与面圈有关,还与其不可收缩圈有着一一对应性。     

临界极大外平面图

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

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

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

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

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

环面上外可平面图的最小圈基

研究环面上2-连通外可平面图G在嵌入∏的面宽fw(G)≥2时的圈基理论;给出在面宽fw(G)≥2和边宽ew(G)＞m,m=max{li|1≤i≤f}时外可平面图G的最小圈基的结构,其中f记为∏的除Hamilton圈外的面迹数,l1,…,lf为∏的对应面迹的长;并证明了G的最小圈基与其不同伦的两条长度之和最短的不可收缩圈之间存在一一对应.     

外平面图的一个结构定理

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

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

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

外平面图的完备染色

设Ｖ（Ｇ）、Ｅ（Ｇ）和Ｆ（Ｇ）分别为平面图Ｇ的点集、边集和面集。Ｇ的完备色数Ｘｃ（Ｇ）是使得Ｖ（Ｇ）∪Ｅ（Ｇ）∪Ｆ（Ｇ）中相邻或相关联的元素间均染不同色的最少颜色数。本文证明了：对无割点的外平面图Ｇ，有Ｘｃ（Ｇ）≤ｍａｘ｛７，△（Ｇ）＋１｝，其中△（Ｇ）为Ｇ的最大度数。     

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

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

两类几乎外平面图的双约束边色数

阐述了几乎外平面图的概念与特点,证明两类特殊的几乎外平面图的双约束边色数恒满足max{Δ(G),FM(G)}≤χe/vf(G)≤max{Δ(G)+1,FM(G)+1},其中Δ(G)、FM(G)分别为图G的最大度和最大面度.     

1-树与外平面图的无圈边着色

设f是图G的一个正常边着色,若在f下G中没有2-色圈,则称f是图G的一个无圈边着色,其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图,无圈边色数不超过其最大度加2。本文证明了该猜想对1-树与外平面图成立,且它们的色数均不超过最大度加1。     

若干n重积图的点可区别边色数

通过研究若干n重积图的边色数及点可区别边色数,就可证明■(Gi)=△(Gi),i=1,2,L,n,则∑=′×××=■△(G_i)其中G1×G2×L×Gn为G1,G2,L,Gn的n重积图.     

图的三类色数之间的一些关系

本文研究图与其补图的三类色数之间的关系,得到了满意的结果。     

几种特殊图形的分数色数研究

图的着色问题是图论中的一个重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用.本文研究了一些特殊图形的分数色数,给出了计算这些图形分数色数的公式,并且对公式进行了证明.     

n个图的逻辑积的色数和边色数

证明了图的逻辑积的色数公式ｘ（Ｇ１∧Ｇ２∧…∧Ｇｎ）≤ｍｉｎ｛ｘ（Ｇ１），ｘ（Ｇ２），…，ｘ（Ｇｎ）｝，边色数有并作如下猜想：ｘ（Ｇ１∧Ｇ２∧…∧Ｇｎ）＝ｍｉｎ｛ｘ（Ｇ１），ｘ（Ｇ２），…，ｘ（Ｇｎ）｝．     

几类冠图的邻强边色数

图的强染色来自计算机科学,有着很强的实际背景,但确定图的强色数是非常困难的。张忠辅,刘林忠,王建方等研究了图的邻强边染色,并提出了邻强边染色猜想：对任意连通图GG,{y}≥3且G≠C5有△≤X’ax（G）≤△＋2。研究了树、圈、扇、轮、完全二部图及完全图的冠图的邻强边色数;证明了：△≤X’as（G）≤△＋1,且X’as（G）≤△＋1当且仅当G[V△]≠Ф。     

外部平面图的平方图的染色

图G的平方图,记作G^2,是一个以原图的顶点集为顶点集,若原图中两点的距离不大于2则连以边所成的图．本文确定了圈的平方图的色数．对于外部平面图,得到以下结论：设G是一个最大度为△(G)的简单连通外部平面图,G≠C5．则x(G^2)≤△(G) 2．     

关于距离图着色问题一个结果的新证明

利用数论的方法,重新确定了距离图G（Z,D）的圆色数Xc（D）和分式色数Xf（D）,其中D={a,b,a＋b,2（a＋b）}是一个特殊的四元素距离集．     

低度外平面图的点强全染色

图G的一个k-点强全染色是指图G的正常全染色f,若任意x,y∈N[υ],有f(x)≠f(y),简记为k-VSTC,称xT^υ5(G)=min｛k／G有k-VSTC}为G的点强全色数。研究了低度外平面图的点强全染色,证明了对△(G)=3的外平面图G有4≤xT^υs(G)≤5。