广义Petersen图G(n,k)的邻强边染色

研究了若干广义Petersen图G(n,k)的邻强边染色,证明了若n≡0(mod 4),k(≠)0(mod 4),则x'as(G(n,k))=4.     

一类正则图的邻强边染色

研究一类正则图G(n,n,r)(n=1,2(mod 3))的邻强边染色. 用构造性方法给出了一类正则图的邻强边染色, 验证了对|V(G)|≥3的连通图G（V,E）(G(V,E)≠C₅), 有Δ(G)≤χ′_αs(G)≤Δ(G)+2成立.     

一类图的邻强边色数的上界

证明了当图G的最大度Δ(G)恰以n的某个函数为界时,G的邻强边色数χ′as(G)≤│cn│,其中0相似文献   

若干广义Petersen图的邻点可区别全染色

研究了若干广义Petersen图G(n,r)的邻点可区别全染色。 构造性地证明了:若n≡0(mod 4),r0(mod 4)或n≡0(mod 5),r0(mod 5),则G(n,r)的邻点可区别全色数为5。     

三类完全三部图的邻强边染色

文章研究了完全三部图G=kl,m,n(1≤l≤m≤n)在1≤l≤3时的邻强边染色问题,用构造性方法给出了其邻强边色数.论证了对1≤l≤3的完全三部图有Δ(G)≤χ′as(G)≤Δ(G)+2成立.     

关于几类特殊图的冠的邻强边染色

设G是一个简单图,f是G的一个k-正常边染色,又满足对任意的uv∈E(G),都有C(u)≠C(v),则称f为G的一个邻强边染色,简称k-ASEC,且称χas(G)=min{k|G存在k-ASEC}为G的邻强边色数,其中C(u)={f(uv)|uv∈ E(G)}.给出了路.圈、树、完全图、完全二分图、星、扇、轮的冠的邻强...     

一类3-正则图的关联邻点可区别全染色

对简单图G(V,E),f是从V(G)∪E(G)到{1,2,...,k}的映射,k是自然数,若f满足(1)uv∈E(G),u≠v,f(u)≠f(v);(2)uv,uw∈E(G),v≠w,f(uv)≠f(uw);(3)uv∈E(G),C(u)≠C(v);其中C(u)={f(u)}∪{f(uv)|uv∈E(G)};则称f是G的一个关联邻点可区别全染色.给出了一类3-正则重圈图Re(n,m)(m≥2,n≥3且n≡0(mod2))的关联邻点可区别全色数.     

一类广义Petersen图的关联着色

通过研究一类广义Petersen图G(n,k)的关联着色,证明了关联着色猜想对于一类广义Petersen图成立,若n≡0(mod3),k≠0(mod3),则Inc(G(n,k))≤5,其中Inc(G(n,k))表示G(n,k)的关联色数.     

图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 的边色数和邻强边色数.     

若干联图Pm∨Gn的邻点可区别E-全染色

记χat'e(G)为图G的邻点可区别E-全色数.若Pm是m阶的路,Sn是n+1阶的星,且nm≥2,则χate(Pm∨Sn)=4;若Pm是m阶的路,Fn是n+1阶的扇,且m≥2,n≥2,则χate(Pm∨Fn)=5;若Pm是m阶的路,Wn是n+1阶的轮,且m≥2,n≥3,如果n≡0(mod 2),则χate(Pm∨Wn)=5,如果n≡1(mod 2),则χate>(Pm∨Wn)=6;若Pm是m阶的路,Kn是n阶完全图,且n≥4,m≥2,则χate+(Pm∨Kn)=n+2.     

图的邻点可区分染色猜想成立的两个充分条件

简单连通图G的邻点可区分全染色(邻强边染色)是图G的一个正常全(边)染色,并且使得任意两个相邻的点u,v满足C(u)≠C(v),其中C(u)={f(u)}∪{f(uw)|uw∈E(G),w∈V(G)}(C(u)={f(uw)|uw∈E(G),w∈V(G)}).满足图G有一个邻点可区分全染色(邻强边染色)所用的最少颜色数记为χat(G)(χ′as(G)).图G的最大度记为Δ(G).本文给出了χat(G)=Δ(G)+3的一个充分条件和χ′as(G)=Δ(G)+2的一个充分条件.     

联图P_3∨K_(m,n)和C_4∨K_(m,n)的邻强边色数

设计一个具有分支限界技术的算法来研究联图P3∨Km,n和C4∨Km,n的k-邻强边染色,并证明mn-3时它们的邻强边色数均为m+n+3.     

图的相邻强边着色数

如果在一个图的正常边着色中,相邻两点关联的边集所着的颜色集合不同,则称此正常边着色为相邻强边着色.对图G进行相邻强边着色所需要的最小色数称为G的相邻强边着色数,记作X'as(G).给出了相邻强边着色数的两个上界:一是对于任何d-正则图G(d≥3),X'as(G)≤16d;二是如果图G有两个边不交的完美匹配,则X'aa(G)≤3△(G) 1.     

路与路联图的邻强边染色和均匀邻强边染色(英文)

对于图G的一个正常边染色c,如果相邻的点所关联的边集的色集不相等,c称为邻强边染色.图G的邻强边染色所需要的最小值称为图G的邻强边色数.如果每个色类所含的边数最多差一,c被称为均匀边染色,其最小值称为图G的均匀边色数.论文确定了路与路联图的邻强边染色数和均匀邻强边染色数.     

图的邻点可区别星边色数的一个上界

提出了图的邻点可区别星边染色及邻点可区别星边色数χ’ass(G)的概念,并用Lovász局部引理证明了若G=(V,E)是一个最小度为δ(G)≥3的简单无向图,则χ’ass(G)≤「32Δ32?。     

图Cm·Kn的邻强边染色

将顶点集和边集分别为V={vij┃i=1,2,…,m;j=0,1,…,n-1},E={v10v20,v20v30,…,vm0v10}U（Ui-1^m）ijvik┃j≠k,j,k=0,1,…,n-1}的图简记为Cm·Kn.利用图分解和色集置换的方法,给出了图Cm·Kn的邻强边色数。     

路与轮联图的邻强边色数

对一个正常的边染色满足相邻点的色集不同的条件时，称为邻强边染色，其所用最少染色数称为邻强边色数。就路与轮的联图，得到了在m,n任意取值情况下的邻强边色数。     

蛛网图的邻强边染色

蛛网图是一个重要的网络拓扑结构,研究它的染色对于网络权的分配和通信网络的设计有重要的指导作用.利用穷举法和组合分析法讨论了蛛网图的邻强边染色,得到了蛛网图的邻强边色数.