若干图的Mycielskian图的边色数

对图G(V,E),μ(G)称为G的Mycielskian图,若V(μ(G))=V(G)∪{v′|v∈V(G)}∪{w}且w V(G),而E(μ(G))=E(G)∪{uv′|uv∈E(G)}∪{wv′}.研究了路、圈、扇、轮图的Mycielskian图的边色数.     

图Fm△↓Sn的边色数和邻强边色数

对图G的一个正常的k边染色法f，若A↓e∈E(G)，e=uv，{f(uw)|uw∈E(G))≠{f(vw)|vw∈E(G))，则称f为G的一个k-邻强边染色法，k的最小值称为G的邻强边色数．V(Fm△↓Sn)={w}∪{ui|i=1、2，…，m}∪{vv|i=1，2，…，m；j=1，2，…，n)，E(Fm△↓Sn)={wui|i=1，2，…．m}∪{uivu|i=1，2，…，m；j=1，2，…，n}∪{uiui |i=1，2，…，m-1)．本文得到了Fm△↓Sn的边色数和邻强边色数．     

完全图半群与连通图半群

引进了拟完全国半群、完全图半群、连通图半群以及连通元的概念，证明了有限字母在上的自由半群和相应的完全图半群同构；是可换图。另外，给出了ｎ阶连通简单图半群有Ｓ阶完全子图半群的一个充分条件。     

图F_m ▽S_n的边色数和邻强边色数

对图G的一个正常的k边染色法f,若 e∈E(G),e = uv,{f(uw) | uw∈E(G)}≠{f(vw) | vw∈E(G)},则称f为G 的一个k 邻强边染色法,k的最小值称为G 的邻强边色数.V(Fm Sn) = {w}∪{ui | i =1,2,…,m}∪{vij | i =1,2,…,m;j =1,2,…,n},E(Fm Sn) = {wui | i =1,2,…,m}∪{uivij | i =1,2,…,m;j =1,2,…,n}∪{uiui+1 | i =1,2,…,m-1}.　　本文得到了Fm Sn 的边色数和邻强边色数.     

图半群

构造了图半群,并证明两个拟简单图同构的充要条件是其相应的图半群同构;讨论了图半群、子图半群的一些性质;引进有向图半群,并讨论了它与严格有向图的关系.     

图F_m W_n的边色数和邻强边色数

给出了FmWn的定义,研究了FmWn边染色和邻强边染色,得出了FmWn的边色数和邻强边色数.     

图F_m▽F_n的边色数和邻强边色数

V(Fm Fn)={w}∪{ui|i=1,2,…,m}∪{vij|i=1,2,…,m;j=1,2,…,n},E(Fm Fn)={wui|i=1,2,…,m}∪{uivij|i=1,2,…,m,j=1,2,…,n}∪{uiui+1|i=1,2,…,m-1}∪{vijvij+1|i=1,2,…,m;j=1,2,…,n-1}对图G的一个正常的k边染法f,若 e∈E(G),e=uv,{f(uw)|uw∈E(G)}≠{f(uw)|uw∈E(G)}则称f为G的一个k-邻强边染色法,k的最小值称为G的邻强边色数。本文得到了Fm Fn的边色数和邻强边色数。     

关于图的3—边色数

本文定义了图的r—边色数,研究了一般图的3—边色数的界和一些特殊图类的3—边色数,给出了图与其补图的3—边色数之间的关系。     

图Fm(△)Sn的边色数和邻强边色数

对图G的一个正常的k边染色法f,若(≯)e∈E(G),e=uv,{f(uw)|uw∈E(G)}≠{f(vw)|vw∈E(G)},则称f为G的一个k-邻强边染色法,k的最小值称为G的邻强边色数.V(Fm(△)Sn)={w}∪{ui|i=1,2,…,m}∪{vij|i=1,2,…,m;j=1,2,…,n},E(Fm(△)Sn)={wui|i=1,2,…,m}∪{uivij|i=1,2,…,m;j=1,2,…,n}∪{uiui+1|i=1,2,…,m-1}.本文得到了Fm(△)Sn的边色数和邻强边色数.     

系列平行图的边色数

Vizing(1964年）和Gupta（1966年）各自独立地证明了边着色中的重要定理：对任何简单图G,表X′（G）＝△或X′（G）△＋1。但确定一个图G的边色数仍是一个尚未解决的问题。本文利用系列平行图的结构性质,确定了它的边色数。     

图的点可区别无圈边色数的一个上界(英文)

图G的一个正常边染色f,若满足:1)G中无2-色圈;2)对于V(G)中的任意两点u和v,有C(u)≠C(v),这里C(u)={f(uw)|uw∈E(G)},则f叫做图G的一个点可区别无圈边染色.图G的点可区别无圈边色数,记为χ′_(vda)(G),是图G的一个点可区别无圈边染色所用色的最小数目.证明了若图G是一个最小度不小于5,且顶点数不超过30Δ~4的图时,χ′_(vda)(G)≤10Δ~2,其中Δ是图G的最大度.     

PmVPn的点可区别边色数

研究了Pm V Pn的点可区别边染色,并得到了PmVPn的点可区别边色数.     

图P_m V W_n的点可区别边色数

对图G的正常边染色,若满足不同点的点所关联边色集合不同,则称此染色法为点可区别的边染色法,其所用最少染色数称为该图的点可区别边色数．得到了路与轮的联图的点可区别边色数．     

图的集合边色数

给出了集合边色数的定义。运用结构图论的方法,给出了集合边色数的下界以及图与其顶点删除子图、边删除子图的集合边色数的关系。     

森林的松弛竞赛色数

主要研究森林的松弛竞赛色数。用分离策略证明了对任意的树G ,当松弛量d =2时 ,它的松弛竞赛色数 χdg(G) =2。这个结果回答了Dunn和Kierstead[4] 提出的问题     

I(Cn)的圆色数

讨论了n-圈Cn的关联图I(Cn)的结构性质.证明了I(Cn)是4-正则的平面图并研究了其色数.主要研究I(Cn)的圆色数并得到结果:如果n=3m,则χc(I(Cn))=χ(I(Cn))=3;如果n=3m 2,则χc(I(Cn))=(6m 4)/(2m 1).当n=3m 1时,给出了χc(I(C3m 1))的一个界.     

带限制的信号分配问题与半星色数

通过研究带限制的信号分配问题定义了半星色数．并最终解决了手机信号的最优分配问题．找到了半星色数与色数、星色数的密切关系．     

外平面图的松弛竞赛色数

主要研究外平面图的松驰竞赛色数。如果缺陷度d =2 ,3 ,4 ,k =7-d ,我们能够分别给Alice一个策略 ,使得对 (k ,d) 松弛染色竞赛Alice能赢。     

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

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

计算圆色数的混合整数规划方法

通过讨论圆色数几个等价的定义,建立了一个求解圆色数χc(G)近似值的混合整数规划,并进一步给出了圆色数χc(G)的精确值．之后,利用这些结果计算了一类特殊图的圆色数χc(G),确定了此类图的圆色数的精确值．