某些平面图的最小折数

讨论了4类4-正则平面图的最小折数纵横扩张.     

几类4-正则平面图的最小折数纵横扩张

主要讨论了4类4-正则图的最小折数纵横扩张,对任意阶这样的的4-正则图都给出了它的一个最小折数纵横扩张,并给出了最小折数与阶数之间的关系.     

一类4-正则图的最小折数纵横扩张

纵横嵌入是图论中的一个有很强应用背景的问题。作为其基本的一步就是研究一个嵌入的纵横扩张。虽然确定最小折数扩张已经从理论上得到了解答，但并未给出很好的算法。本文提供了这方面的一些结论，并进一步研究了一类4－正则图g，得到了确定这类图最小折数纵横扩张的一个线性算法。     

一类4-正则图的最小折数纵横扩张

提出了一类新的4-正则图,并讨论了其最小折数纵横扩张,设计出求最小纵横扩张的线性时间算法,给出了最小折数与阶数之间的关系.     

两类4-正则图的最小折数纵横扩张

纵横嵌入的理论已被用在超大规模集成电路的设计中.确定最小折数扩张已经从理论上得到了有效算法.本文作者在这一理论的基础上,进一步研究了两个特殊的4-正则图类,得到了确定这两类图的最小折数纵横扩张的简便算法,并给出了这两类图的纵横扩张的最小折数.     

平面图正常4—着色数的一个计算公式

四色定理等价于任何准极大平面图（near-triangulation）至少有一个正常4－着色。给出了对任意给定的准极大平面图都能准确求出其正常4－着色数的计算公式,该公式的复杂性揭示了四色定理本身所蕴涵的难度。为研究四色定理提供了一条与以往不同的途径。     

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

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

平面图平方的最小度

设G是一个没有4-圈的平面图,G的平方图G2定义在V(G)上,使得2个点u和v在G2中是相邻的当且仅当它们在G中的距离为1或2.证明了:δ(G2)≤Δ(G) 33,并且当δ(G)≥4时有δ(G2)≤16.其中,δ(H)和Δ(H)分别表示图H的最小度和最大度.     

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

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

开外平面图的边面全色数

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

一些平面图的无圈边染色

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

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

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

不含特殊短圈平面图的无圈边染色

无圈边染色是指图G的一个正常边染色,使其不产生双色圈.研究了不含特殊短圈平面图的无圈边染色问题,证明了：如果平面图G不含4到8-圈,那么G的无圈边染色数不大于Δ（G）＋1.     

平面图的无圈边染色

一个图G的无圈边染色是一个正常的边染色,使得不产生双色圈.Fiamˇcik和Alon等分别提出了著名的无圈边色数猜想:每一个简单图G是无圈边(Δ+2)可染的,其中Δ是G的最大度.证明了对于不含3圈和5圈相邻的平面图猜想成立.     

不含三角形的平面图的无圈边染色

图的无圈边染色是图的染色理论中的一个重要问题.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度.为了深入研究该猜想对平面图是否成立,利用差值转移方法并结合最小反例图的一些结构性质,证明了:不包含三角形的平面图G,如果其最大顶点度不小于6,则其无圈边色数不超过Δ(G)+3.     

射影平面上外可平面图的最小圈基

研究了射影平面上2 连通图的圈基结构,并给出了在嵌入的边宽度ew(G)≥5时外可平面图的最小圈基结构,证明了最小圈基与最短不可收缩圈之间的一一对应性.     

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

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

最大度为4的外平面图的无圈边色数

一个图G的无圈边染色是一个正常的边染色,使得任一个圈上至少有3种不同的颜色.G的无圈边色数a＇（G）是使得G有无圈k-边染色的最小整数k.设G是一个最大度为4的外平面图.对于现有结果 4≤a＇（G）≤5中,何时为4,何时为5,还没有一个完整的刻画.给出一个使得a＇（G）=4的充分条件,拓展了该领域的相关结果.     

几类平面图的集合色数

设G是非平凡连通图,记c:V(G)→N是G的一个顶点染色,这里相邻的两个顶点可以着相同的颜色。对于图G的任一顶点ν,与ν相邻的顶点所着颜色的集称为邻色集,记NC(ν)。如果G中任意相邻的两个顶点ν,u满足NC(u)≠NC(ν),则称c是G的一个集合染色。集合染色所需的最少的颜色数称为G的集合色数,记χs(G)。本文给出了团数是3的平面图,没有4圈的平面图及烟花图和风车图的集合色数。     

优化正则图的限制边连通性的最小度条件

限制边割将连通图分离成不合孤立点的不连通图，如果最小限制边割只能分离孤立边，则称图G是超级限制边连通的．证明了如果k＞|G|/2 1，那么k正则连通图G是超级限制边连通的，k的下界在一定程度上是不可改进的．