较大亏格曲面嵌入图的线性荫度

通过度再分配的方法研究嵌入到曲面上图的线性荫度.给定较大亏格曲面∑上嵌入图G,如果最大度Δ(G)≥((45-45ε)^(1/2)+10)且不含4-圈,则其线性荫度为[Δ/2],其中若∑是亏格为h(h>1)的可定向曲面时ε=2-2h,若∑是亏格为k(k>2)的不可定向曲面时ε=2-k.改进了吴建良的结果,作为应用证明了边数较少图的线形荫度.     

一类新图类的可定向嵌入的亏格分布

在刘彦佩提出的联树法的基础上,通过分类一类新图类的可定向嵌入曲面求出了这类图类的可定向嵌入的亏格分布.所用方法与国际上现有方法不同,且易于推广,所考虑的非平面图类比已有计算图的嵌入亏格分布文献中的非平面图更复杂.     

一类图在环面上的嵌入

图的亏格分布已被证明为NP难问题,对于大部分图类的亏格分布和完全亏格分布,暂时还没有得到.而图在不同亏格曲面上的不等价的嵌入个数往往有一定的相关关系,因此研究图在小亏格曲面上的嵌入问题对于研究图类的亏格分布也就有着重要意义.本文利用嵌入联树模型得到了由鹅卵石路图添加1条边所得到的一类图nG在环面上的嵌入个数为4n-1+(11n-29)2n-3(n≥2).     

复杂三维流形的两类四穿孔球面和

在邱瑞锋、王诗宬和张明星证明了可定向闭曲面加厚及某些复杂三维流形的平环和具有亏格可加性的基础之上,从2个可定向闭曲面加厚沿着不可压缩四穿孔球面进行黏合出发,利用三维流形组合拓扑的讨论技巧和方法,通过分析四穿孔球面在相黏可定向闭曲面加厚上的2种不同分离形式,证明了可定向闭曲面加厚及某些复杂三维流形的两类四穿孔球面和具有亏格可加性,将复杂三维流形某些带边曲面和具有亏格可加性推广到更加一般的情形.     

曲面可扩性的一个注解(英文)

推广了Aldred,Kawarabayashi and Plummer关于曲面上图的可扩性的结果.证明了,如果|V(G)|8g(G)-8/k-3或|V(G)|4g(G)-8/k-3(k≥4),那么G不是k-可扩的,其中g(G)和g珘(G)分别是G可定向亏格及不可定向亏格.     

Cm,n的最小亏格与Km,n的强嵌入

令C_m,n表示长为m的圈与n个孤立点的联结(join)所得的图. 本文证明了C_m,n的最小亏格和最小不可定向亏格与完全二部图K_m,n的相等. 同时,证明当m≥2并且n≥2时, K_m,n在其最小可定向曲面上有一个强嵌入; 当m≥3并且n≥3,时, 在最小不可定向曲面上有一个强嵌入.     

G的立方图G~3的上可嵌入性

自从Nordhaus,Stewart和White[1]等引入图的最大亏格以来,图的最大亏格以及图的上可嵌入引起了广泛关注.而图的最大亏格rM(G)是指最大的整数k使得图G的一个2 胞腔嵌入到可定向的曲面Sk上.因为图在任意可定向曲面上的2 胞腔嵌入中至少有一个面,关于图的上可嵌入性,刘彦佩[2],Xuong[3]和Nebseky[4]分别给出不同形式的充要条件.主要证明下述结果:设G是一个简单图,则G3是上可嵌入的.特别地,当k≥4时,Gk也是上可嵌入的.     

某些三维流形中的不可压缩曲面

设 M是一个不同胚于固体环的可定向边界可约化的三维流形或一个亏格大于 1的不可定向柄体 .证明 M中含有任意大亏格的不可压缩曲面     

可定向闭曲面上最大阶保定向周期映射的唯一性

A．Wiman和W.J.Harvey证明了在亏格为g,g≥2的可定向闭曲面上，保定向周期自同胚的最大阶是4g 2。本文中我们研究了这样的映射的唯一性。我们证明曲面的自同构群的由这样的映射生成的4g 2阶循环子群在共轭意义上是唯一的。     

G的立方图G3的上可嵌入性

自从Nordhaus，Stewan和White等引入图的最大亏格以来，图的最大亏格以及图的上可嵌入引起了广泛关注．而图的最大亏格rM(G)是指最大的整数k使得图G的一个2-胞腔嵌入到可定向的曲面Sk上．因为图在任意可定向曲面上的2-胞腔嵌入中至少有一个面，关于图的上可嵌入性，刘彦佩，Xuong和Nebseky分别给出不同形式的充要条件．主要证明下述结果：设G是一个简单图，则G^3是上可嵌入的．特别地，当k≥4时，G^4也是上可嵌入的．     

可嵌入到欧拉示性数非负的曲面图的线性荫度

图G的线性荫度是一种非正常的边染色,即它的边集合E(G)可以分割成线性森林的最小数量,用la(G)表示。主要研究最大度Δ(G)≥7且可嵌入到欧拉示性数非负曲面图G上的线性荫度,证明了如果图G中不含相邻的含弦6-圈,则图G的线性荫度为「Δ/2。     

无4-圈和5-圈的平面图的k-frugal列表染色

在图G的一个正常点染色c中,对于图中任意一点v,如果每种颜色在点v的邻点中至多出现k-1次,这个染色就称为图G的一个k-frugal染色。关于无4-圈和5-圈的平面图的k-frugal列表染色问题,有以下两个结论:(1)对于一切不含4-圈和5-圈的平面图,如果其最大度满足Δ≥3k+8,其k-frugal列表色数小于等于「Δ/(k-1)+2;(2)一切不含4-圈和5-圈的平面图,则其k-frugal列表色数小于等于「Δ/(k-1)+5。     

围长至少为6的曲面图的列表单射染色

图G的一个点染色称为单射染色,如果任何两个有公共邻点的顶点染不同的颜色.一个图G称为单射k-可选择的,如果对于顶点V(G)的任何一个大小为k的允许颜色列表L,都存在一个单射染色φ,使得对于v∈V(G),有φ(v)∈L(v).使得G为单射k-可选择的最小k,称为G的列表单射染色数,记作χ_i~l(G).设G是最大度为Δ,围长为g的可嵌入到欧拉示性数χ(Σ)≥0的曲面Σ的一个图.证明了若Δ≥7且g≥6,则χ_i~l(G)≤Δ+3.     

不含4圈的平面图的无圈边染色

如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数。利用已有的关于平面图的结构性质,证明了不含4圈的2-连通平面图的无圈边色数不超过Δ(G)+11。     

不含3圈的平面图的无圈边染色

图的无圈边染色是图的染色理论中的一个重要问题,2001年,Alon等猜想任意简单图G的无圈边色数都不超过△（G）＋2,其中△（G）为图G的最大顶点度。为了研究该猜想对平面图是否成立,利用差值转移方法,证明了不包含三角形的平面图G的无圈边色数不超过△（G）＋3．     

双外平面图的点染色

图染色问题是图论研究中的重要问题之一,本文针对双外平面图G的点色数进行研究,并证明了：（1）不加剖分点时,当顶点数为6n＋k（n=1,2,…）（k=1,2,3）时,xv=4;否则xv=3.（2）xv=4时,当在相同面上两端的顶点标号冲突时,若剖分点加在这个标号相对的边上时,仍然有xv=4;否则xv=3.     

伪Halin-图的无循环边着色

图G的无循环边着色是指图G的正常的边着色且任意的圈上不着双色.图G的无循环边色数是指对G进行无循环边着色所需的最少色数k,记为a′(G).给出了伪Halin图的无循环边色数满足猜想a′(G)Δ(G)+2,并且对任意的伪Halin图G且G≠K4,有a′(G)=Δ(G).     

(P~2)_n和(P~3)_n的D(3)-点可区别全染色

图的染色问题是图论研究的经典领域,在网络结构和实际生活中都有着广泛的应用,随着计算机和通讯、电力网络的日益发展,染色问题成为近年来图论研究的热点.图的D(β)-点可区别全染色又是染色问题中的难点.通过分类讨论、归纳探究,在图的点边集合与色集合间构造了一种一一对应关系.讨论了幂图Pkn(k=2,3)的点可区别全染色,使得距离不大于3(D(3))的任意2点都有不同的色集合,得到幂图Pkn(k=2,3)的D(3)-点可区别全染色数.     

不含4圈的平面图的无圈边色数的新上界

 为了研究平面图的无圈边染色,利用差值转移方法并结合平面图的结构性质,证明了不含4圈的平面图的无圈边色数不超过Δ(G)+6.     

图的最大亏格与面度

利用图在曲面上的嵌入特征,特别是面的度的大小,研究图的最大亏格的下界.