共查询到18条相似文献,搜索用时 203 毫秒
1.
一个图G的无圈边染色是一个正常的边染色,使得任一个圈上至少有3种不同的颜色.G的无圈边色数a'(G)是使得G有无圈k-边染色的最小整数k.设G是一个最大度为4的外平面图.对于现有结果 4≤a'(G)≤5中,何时为4,何时为5,还没有一个完整的刻画.给出一个使得a'(G)=4的充分条件,拓展了该领域的相关结果. 相似文献
2.
特殊平面图的全染色 总被引:1,自引:1,他引:1
孙向勇 《山东师范大学学报(自然科学版)》2007,22(1):10-12
给定一个图G,G的全k染色是指至多用k种颜色,对G的顶点和边同时进行染色,使得相邻的或相关联的两个元素(点和边)不染同一种颜色.图G的全染色数xT(G)是指使G全k染色的最小整数k.Δ(G)是G的最大度,本文对不含从4到k的圈,且3-圈不重点的平面图得出的结论有:如果(Δ,k)分别是(6,4),(5,5),(4,11),则G的全染色数是Δ 1. 相似文献
3.
图 G 的星边染色是指 G 的一个正常边染色满足 G 中无长为4的路(或圈)是2-边染色的.使得图 G 有星边染色的最小颜色数 k 称为 G 的星边色数,记为 χ′st (G ) .证明了若平面图 G 不含4-5-圈且无相交3-面,则χ′st (G )≤ [1.5]Δ + 10 相似文献
4.
该文主要证明了若G=(V1,V2:E)是一个满足|V1|=|V2|=n≥sk的二分图,其中k,s,n为3个正整数且k≥2,s≥4,如果σ1,1(G)σ2[(1-1/s)n+k],那么对G的任意k条独立边e1,…,ek,G有一个包含k个点不交的圈C1,…Ck的2-因子,使得ei∈E(Ci),且|Ci|≥2s. 相似文献
5.
图G的k-全染色是用k种颜色对图G的V(G)∪E(G)中的元素进行着色, 使得相邻或者相关联的两个元素染不同的颜色, 图G的全色数是使G存在k-全染色的最小整数k. 对最大度为Δ的平面图, 如果(1),Δ(G)≥5且任何点至多关联一个长度至多为5的圈, 或者(2),Δ≥4, 不含3-圈并且任何点至多关联一个长度至多为6的圈, 则它的全色数为Δ(G)+1。 相似文献
6.
马刚 《安徽大学学报(自然科学版)》2017,41(4)
对图G的一个正常边染色,如果图G的任何一个圈至少染3种颜色,则称这个染色为无圈边染色.若L为图G的一个边列表,对图G的一个无圈边染色φ,如果对任意e∈E(G),都有φ(e)∈L(e),则称φ为无圈L-边染色.用a′_(list)(G)表示图G的无圈列表边色数.论文证明:若图G是一个平面图,且它的最大度Δ≥5,围长g(G)≥7,则a′_(list)(G)=Δ. 相似文献
7.
设 G 是一个含有4k 个顶点的简单图,若δ(G)≥2k,则 G 包含 k -2个4-圈和1个8-圈,使得这 k -1个圈是相互独立的。在此基础上证明了:若 G 是一个含有4k(k≥4)个顶点的图,δ(G)≥2k,则下列两种情况中至少有一种成立:(1)G 包含 k -3个4-圈和1个12-圈;(2)G 包含 k -4个4-圈和2个8-圈。且不论哪一种情况成立,这k -2个圈点不交。 相似文献
8.
令G=(V,E)是一个图,M是边集E(G)的子集,如果有e∈E(G)/M,e至少与M中一条边相连,则称M为图G的边控制集,进一步,若M是匹配,则称M为图G独立边控制集,本文给出关于边控制集的一些结论。(1)设图H,S是两中连勇图,且H,S∈ж,γe(S)=1,M和M′={uv}分别是图H和S的唯一最小边控制集,其中S是图1中的(G1,G2,G3,G4)四个图之一,对任何点x∈V(S)={u,v},y∈V(H)-V(M),令G=H(y=s)S,则G∈ж,(2)如果连通图G≠K2,G∈ж,γe(G)=k,则存在G的两个连通于图H,S和某两个正整数l,m使H∈ж,S∈ж,且γe(H)=k-l,γe(S)=l,G≌H(yi=xi)S,其中l≤i≤m. 相似文献
9.
图 G 的一个正常[k]-全染色是一个映射:V∪E→{1,2,…,k},使得 V∪E 中任意一对相邻或者相关联元素染不同颜色。用 f(v)表示点 v 及所有与其关联的边的颜色的加和,若对任意 uv∈E(G),有 f(u)≠f(v),则称该染色为图 G 的[k]-邻和可区别全染色。k 的最小值称作图 G 的邻和可区别全色数,记为 tndiΣ(G)。Pils'niak 和Woz'niak 提出猜想:对任意简单图 G,有 tndiΣ(G)≤Δ(G)+3,其中Δ(G)为图 G 的最大度。图 G 的最大平均度,记为 mad(G),是 G 的所有非空子图的平均度的最大值。运用组合零点定理和权转移方法,证明了若Δ(G)=3且mad(G)<125,或Δ(G)=4且 mad(G)<52,则 tndiΣ(G)≤Δ(G)+2。 相似文献
10.
对于最大度是Δ的可平面图G,如果χ′(G)=Δ称G为第一类图,如果χ′(G)=Δ+1称G为第二类图,χ′(G)表示G的边染色数.1965年,Vizing举例说明,最大度是4的平面图中不仅有第一类图,也有第二类图.论文运用Discharge方法及临界图的重要性质证明:最大度是4,不含5圈和6圈,且任意两个相交面的度不相同的可平面图是第一类图. 相似文献
11.
郑丽娜 《浙江师范大学学报(自然科学版)》2012,(1):32-36
无圈边染色是指图G的一个正常边染色,使其不产生双色圈.研究了不含特殊短圈平面图的无圈边染色问题,证明了:如果平面图G不含4到8-圈,那么G的无圈边染色数不大于Δ(G)+1. 相似文献
12.
图的点可区别无圈边色数的一个上界(英文) 总被引:2,自引:0,他引:2
图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的最大度. 相似文献
13.
伪Halin-图的无循环边着色 总被引:1,自引:0,他引:1
图G的无循环边着色是指图G的正常的边着色且任意的圈上不着双色.图G的无循环边色数是指对G进行无循环边着色所需的最少色数k,记为a′(G).给出了伪Halin图的无循环边色数满足猜想a′(G)Δ(G)+2,并且对任意的伪Halin图G且G≠K4,有a′(G)=Δ(G). 相似文献
14.
主要研究了平面图的无圈边染色问题。证明了对平面图G,如果G不包含3,5圈,且G中任意两个4-圈都不共边,则无圈边染色猜想成立;并且,如果G不含3-圈,且任意两个4-圈不共点,则G的无圈边染色数不大于Δ(G)+3。 相似文献
15.
16.
张艳 《吉林大学学报(理学版)》2020,58(3):575-589
图G的平方G2定义为顶点集V(G)=V(G2), 并且uv∈E(G2)当且仅当u和v之间的距离至多为2. G2的色数χ(G2)是指使得G2存在正常k顶点染色的最小整数k. 用权转移的方法证明: 如果mad(G)<4且Δ(G)≥7, 则χ(G2)≤3Δ(G)+1;
如果mad(G)≤4且Δ(G)≥8, 则χ(G2)≤3Δ(G)+5. 相似文献
17.
丁伟 《山东大学学报(理学版)》2012,47(6):76-79
如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数。利用已有的关于平面图的结构性质,证明了不含4圈的2-连通平面图的无圈边色数不超过Δ(G)+11。 相似文献
18.
一类正则图的邻强边染色 总被引:1,自引:0,他引:1
研究一类正则图G(n,n,r)(n=1,2(mod 3))的邻强边染色. 用构造性方法给出了一类正则图的邻强边染色, 验证了对|V(G)|≥3的连通图G(V,E)(G(V,E)≠C5), 有Δ(G)≤χ′αs(G)≤Δ(G)+2成立. 相似文献