两类特殊图的泛宽度染色

研究了图染色问题中与频道分配有关的泛宽度染色.给出了两类特殊图的泛宽度色数.     

几个特殊图的泛宽度色数

设G是一个简单图,i是一个正整数,X是V（G）的一个子集,如果X中任意两个点的距离都大于i,则称X是一个i-宽度箱,i叫做X的宽度,一个图G的泛宽度色数xp（G）是使得G的顶点集V（G）被剖分成宽度两两不同的k个宽度箱的最小整数k,本文给出了轮,扇及图Kn的推广的hajos sum的泛宽度色数,     

图的无圈染色

我们证明最大度Δ≥5的图的无圈色数至多是a(G)≤L(Δ-1)2/2」,这个结果比目前公认的最小上界a(G)=Δ(0-1)/2要小。同时得出两个新的结论:对任意Δ=5的图G,有a(G)≤8;对任意Δ=6的图G,有a(G)≤12。     

图的无圈边染色的一个结果

为了研究简单图G的无圈边染色,利用线性一时间算法思想证明了最大顶点度为4的简单图G。如果G中任意一条边的两个端点的度数之和不超过6,则其无圈边色数不超过5。     

两类n-部图及其补图的无圈染色

图G的无圈染色是满足任意两个色类的并的导出子图不含圈的正常点染色.G的无圈染色所用最少的颜色数称为G的无圈色数,记为a(G),从而得到了两类n-部图及其补图的无圈色数.     

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

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

圈龙图的星边染色

通过分析圈龙图的结构,利用组合分析法及反证法讨论了圈龙图的星边染色,通过构造具体染色得到了圈龙图的星边色数.     

一类图的几乎唯一泛圈性

设G是阶为n的简单Hamilton图,若存在m（3m〈n）使对每个l∈{3,4,…,n}-{m},G恰有一个长为l的圈且不含长为m的圈,则称G是几乎唯一泛圈图．用Гk^（3）表示具有n＋k条边且满足一定条件的简单外可平面的日图的集合,讨论了Гk^（3）中图的几乎唯一泛圈性．     

基于最大平均度的图的无圈边染色

为研究图的无圈边色数与图的最大平均度之间的关系,利用差值转移方法和最小反例图的一些结构性质,证明了最大平均度不小于7/2的简单图G,如果其最大度不小于6,则其无圈边色数不超过Δ(G)+2.     

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

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

几种图的对策着色和对策色数

介绍了一种新的色对策和对策色数,比较了2种色对策的差异.对几种特殊的图形的色对策数进行了讨论,运用顶点标号方法,给出获胜策略.     

具有给定色数的互补图的实现

本文给出关于三元组(p;m,x)的充分必要条件,在此条件下,存在p点的图G,使图G及其补图()的点色数(或边色数)分别是m和n。     

图上的对策着色和对策着色数

图G的对策色数Ⅱχg(G)是由图的点色数χg(G)拓展而来的.本文对几类特殊的图进行了讨论,分别给出了图Qn,Gn以及与圈有关图的对策色数Ⅱ,并给出了选手Alice相应获胜的对策.     

点可区别边色数和点可区别全色数的两个上界

应用概率方法中的第一矩量原理和Markov不等式,证明了对于最大度为Δ的n阶图G,当Δ≥2时,其点可区别的边色数χv′d(G)≤nΔ(n-1),当n≥3,Δ≥1时,其点可区别的全色数χvt(G)≤2 nΔ(n-1).     

特殊图的条件染色

对于一个正整数r，图G的一个条件（k，r）-染色是使得图G的每个度至少为r的顶点至少与具有r种不同颜色的顶点相邻的正常的顶点染色．使图有一个条件（k，r）-染色的最小的整数k是图的第r个条件色数Z，（G），本文给出了对于不同的正整数，路、扇、轮的条件色数。     

Wm V C3的点可区别正常边色数

对于轮和圈的联图，给出了一种点可区别的边染色方法，并得到了其点可区别边色数．     

Halin图和Series-Parallel图的动态色数

图的动态着色是Bruce Montgomery于2001年引入的一个新概念。本文分别证明了Halin图和非5圈的Series—Parallel图的动态色数都不超过4。     

图的色数与着色数的上界

证明了对于围长不少于2k1的图G,其色数X(G)≤c((bk,2k+1+2)n)1/k+1+2,其中c=c(k)且limk→∞ c(k)=1,bt,k是G的booksize.另外还证明了对于围长不少于2k+1的图G,其着色数σ(G)≤[bk,2k+1+1)n/2]1/k+2.     

路和圈的广义Mycielski图的邻强边色数

研究了路和圈的广义Mycielski图的邻强边染色,证明了对P个点的路Pp≥2),Xa(Mn(Pp))={4 p=3.对圈Cp,有Xa(Mn(Cp))=5.