平面图的强边染色的一个结果

如果图G的一个正常边染色的任意有公共邻边的两条边的染色不相同,则它是图G的一个强边染色。图G的强边染色所需要的最小颜色数称作图G的强边色数。本文利用差值转移方法证明了最大顶点度为偶数且不小于6的平面图,如果其不含有3圈,则其强边色数不超过5△2/4,特别地,本文证明了最大顶点度为4的平面图,如果其围长不小于5,则其强边色数不超过20。     

没有短圈的平面图的强边染色

图G的强边染色是在正常边染色的基础上,要求长为3的路上的任意两条边染不同的颜色,强边染色所用颜色的最小整数称为图G的强边色数.众所周知,平面图的强边色数至多是4Δ+4.文章首先给出极小反例的构型,然后通过权转移法,证明了没有3-,5-,6-,7-,8-圈及相交4-圈的平面图的强边色数至多是3Δ+1.     

一类平面图的强边着色

图G的强边着色是正常边着色且任何长为3的路的边不着双色.图G的强边色数是G的所有强边着色中使用色数的最小者,记为χ′s(G).证明了如果图G是平面图且满足g(G)≥14,则χ′s(G)≤|(5Δ2-2Δ+1)/4|,其中g(G)表示图G的围长.     

广义Petersen图P(3n,n)的强边染色

研究了一类广义Petersen图P(3n, n)的强边染色问题,得到的结果为:6≤χs′(P(3n, n))≤8,这里χs′(P(3n,n))表示P(3n, n)的强边色数.特别地,当n为偶数,并且n≡1或2(mod 3)时,χs′(P(3n, n))=6.     

一类平面图的强边染色

图G的强边染色是指对图G的边进行染色,使得距离不超过2的任意两条边染不同的颜色. 任何一个平面图都可用4Δ+4种颜色进行强边染色. 证明了当平面图没有k-圈(4≤k≤10)且3-圈不相交时(即每个顶点至多关联一个3-圈), 必定存在一个3Δ+1种颜色的强边染色.     

最大度等于5的图的强边色数

最大度等于5的图的强边色数至多为38.     

关于最大度是4的平面图的18-强边染色

图G的强边染色是一种边染色使得任何长至多为3的路上的边都染不同的颜色.使得图有一个强边染色的最小颜色数称为图的强边色数.当图G是平面图且最大度为4时,Wang等人证得其强边色数不超过19.在本文中,我们证明:对最大度为4的平面图,若它是一个非18-强可染的边数极小图,则它一定不存在至多含三条边的非平凡边割.     

高度正则图的强边色数

设f是图G的一个正常边着色，若对G中任意不同的两点u,v，着在与u关联的边上的色集和着在与v关联的边上的色集不同，则称f为强边着色。满足此条件的最小色数称为G的强边色数，记为X^-′（G）。本文确定了对n阶（n-2）-度正则图G，X^-′（G）=n，当n≥6时，对其补图为Hamilton圈的n阶（n-3)-正则图G，X^-′（G）=n-1，还给出了对任意的一条边e，X^-′（G-e)≤X^-′（G） 1的一个充分条件和X^-′（G-e）=X^-′（G） 2的必要条件。     

△（G）=3的图的列表强边染色

证明了若G为△（G）=3的图，则强边选择数SХl＇（G）≤11．     

完全图K_m与路P_n的笛卡尔积的强边色数

图G的强边染色是指任意相邻与同一条边的两条边不能染相同的颜色的一种正常边染色.一个图G的强边色数χ'_s(G)是G的所有强边染色中所用颜色最少的强边染色使用颜色的数目.研究完全图K_m与路P_n的笛卡尔积K_m×P_n的强边染色问题,证明χ'_s( K_m×P_n)=1/2(m~2+3m),其中n≥2,m≥2.     

一类图的列表强边染色

给出了列表强边染色的定义,证明了若G为d(x)+d(y)≤5,则强边选择数Sχ′l(G)≤6.     

一类正则二部图的邻强边染色

研究了一类正则二部图的邻强边染色,验证了文献[1]中猜想是正确的.     

几类冠图的邻强边色数

图的强染色来自计算机科学,有着很强的实际背景,但确定图的强色数是非常困难的。张忠辅,刘林忠,王建方等研究了图的邻强边染色,并提出了邻强边染色猜想：对任意连通图GG,{y}≥3且G≠C5有△≤X’ax（G）≤△＋2。研究了树、圈、扇、轮、完全二部图及完全图的冠图的邻强边色数;证明了：△≤X’as（G）≤△＋1,且X’as（G）≤△＋1当且仅当G[V△]≠Ф。     

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

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

一类广义Petersen图的邻强边染色

研究了一类广义Petersen图G(n,k)的邻强边染色,构造性地证明了:若n≡0(mod3),k≡/0(mod3),则χ_(as)~′(G(n,k))=4.其中χa′s(G(n,k))表示G(n,k)的邻强边色数.     

蛛网图的邻强边染色

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

一类正则图的邻强边染色

研究一类正则图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相似文献   

路,圈的倍图的染色问题

通过分类讨论、归纳探究,在图的点边集合与色集合间构造了一种一一对应关系.通过这种新关系,研究了路和圈的倍图的邻强边染色以及路的倍图的均匀邻强边染色,得到相应的色数,并给出了具体的染色方案     

网格图的剖分图的强边染色

研究了3种网格图的剖分图的强边着色.网格图的剖分图是指用一个长为2的路去替换网格图的每条边.具体给出了六边形、四边形、三角形的网格剖分图的一种着色方法,以此为基础证明了Sχ′(Γs6)=4,Sχ′(Γs4)=5,Sχ′(Γs3)=7.