没有合适的资源?快使用搜索试试~ 我知道了~
≤ ≤≥≤≤≤|−|∈∈∈|−| ≥∈− ≥ |−| ≥联系我们可在www.sciencedirect.com在线获取理论计算机科学电子笔记346(2019)53-64www.elsevier.com/locate/entcs星系骨架为1的图的骨架染色卡米拉·阿劳霍,胡里奥·阿劳霍和安娜·席尔瓦2ParGO Group - Paralelism,Graphs and Optimization数学FederalUniversityofCear'aFortaleza,CE -Brazil亚历山大·塞萨尔3Col′egio7deSetembroFortaleza,CE -巴西摘要图G =(V,E)的一个(真)k-染色是一个函数c:V(G)→ {1,., k},使得c(u)c(v),每个UVE(G)。给定图G和G的子图H,(G,H)的q-主干k-染色是k-染色c,使得对每条边uv,E(H)。 (G,H)的q-骨架色数,记为BBCq(G,H),是使(G,H)存在q-骨架k-染色的最小整数k. 类似地,(G,H)的环q-骨架k-染色是一个函数c:V(G)1、......、K这样,对于每一个边缘紫外线E(G),我们有c(u)c㈤1,并且对于每个边uvE(H),我们有kQc(u)c㈤Q. (G,H)的循环q-主干色数,记作CBCq(G,H),是使得存在这样的染色c的最小整数k。本文首先证明了:如果G是一个3色图,F是一个星系,则CBCq(G,F)2 q + 2. 然后,证明了当M是匹配时,对每个q4,CBC3(G,M)7和CBCq(G,M)2q平面图G.此外,我们认为,这两个边界是紧的。这样的界限部分回答了文献中的公开问题。 我们还证明了可以在多项式时间内计算BBC2(G,M),无论何时G是具有匹配主干M的外平面图。最后指出了证明BBC 2(G,M)Δ(G)+1,对任意图G的任意一个匹配环M[M iskufetal. 2010年10月10日,我决定将它修复。关键词:图染色;圆骨架染色;平面图; Brooks1这项工作得到了CNPq/Funcap项目PNE-0112-00061.01.00/16 SPU N:4543945/2016,CNPq Universal项目401519/2016-3和CNPq赠款310234/2015-8,304576/2017-4和134604/2018-0的部分支持。2电子邮件:julio@mat.ufc.br、anasilva@mat.ufc.br和camilasenaraujo@gmail.com3电子邮件:alanzar. gmail.comhttps://doi.org/10.1016/j.entcs.2019.08.0061571-0661/© 2019作者。出版社:Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。54C. Araujo等人/理论计算机科学电子笔记346(2019)531介绍对于基本概念和未定义的术语,我们参考[3]。设G=(V,E)是一个简单图.给定一个正整数k,我们用[k]表示集合{1,···,k}一图G的k-染色是函数c:V(G)→[k]使得c(u)c(v),每个边uv∈E(G).我们说G是k-可染的,如果存在G的k-染色。图G的色数,记为χ(G),是使G是k-可染的最小k.如果χ(G)=k,则称G是k-色的;如果G允许k-染色,则称G是k设G是一个图,H是G的一个子图.我们称(G,H)为一对,其中H称为G的骨架.给定两个正整数q和k,(G,H)的q-骨架k-染色是G的k-染色c,其中|c(u)− c(v)|对每个uv ∈ E(H),有≥ q. (G,H)的q-主干色数记为BBCq(G,H),是(G,H)存在q-主干k-染色的最小k关于主干着色的问题首先由Broersma等人提出[5],基于与频率分配相关的着色问题。如果c是G的一个真k-染色,则定义为g(v)=q·c(v)−(q−1)的g是G的任意生成子图H的(G,H)的一个q-主干(q·k−q+1)-染色。因此BBC q(G,H)≤q·χ(G)−q +1.我们现在考虑特殊的骨干k-着色,其中颜色空间是圆形的,也就是说,它表现为Z/k。 更精确地说,给定图G、G的子图H和正整数q,(G,H)的循环q-骨架k-染色是k-染色c:V(G)→ {1,...,k},使得q≤|c(u)−c(v)|≤k−q,对每个uv∈E(H)。(G,H)的循环q-骨架色数,记为CBCq(G,H),是(G,H)存在循环q-骨架k-染色的最小k注意任何环状q-骨架k-染色都是q-骨架k-染色.同样地,q-骨架k-染色产生环状q-骨架(k+q−1)-染色。因此,我们得到BBC q(G,H)≤ CBC q(G,H)≤ BBC q(G,H)+q− 1,并且还q·x(H)≤ CBC q(G,H)≤ q·x(G).Havet等人 [8]解决了以下问题:猜想1.1如果G是一个平面图,F是G中的一个星系,则CBCq(G,F)≤2 q +2。回想一下,一个有n个顶点的星是一个有n-1个叶子的树,剩下的顶点称为星的中心顶点(在星只是一条边的情况星系是一个图形,它的连接部分是恒星。我们证明了猜想1.1对3-色图成立,甚至对那些不是平面的3-色图也成立。回想一下,对于平面图,根据Grüotzsch我们也知道,有线性时间算法可以找到无三角形平面图的3-着色[9]。通过结合这些算法C. Araujo等人/理论计算机科学电子笔记346(2019)5355利用我们的结果,我们推出了一个具有2个q + 2色的q-骨架染色可以在线性时间内得到。我们不知道当G是无三角形的时,我们的界是否是紧的。当G不是无三角形的时候,它是平凡紧的,因为它以一个K1,3为骨架的K4为因此,我们提出问题:问题1.2如果G是一个无三角形的3-色图,F是G中的一个星系,那么全血细胞计数q(G,F)≤ 2 q +1?关于匹配主链,Havet等人[8]提出了以下问题:问题1.3如果G是平面图,M是G中的匹配,q是正整数,q≥ 3,CBC q(G,M)≤ 2q +1是否成立?在同一篇文章中,他们证明了当M是平面图G中的匹配时,判定CBC2(G,M)≤k(k∈ {4, 5})是NP-完全的.这就是为什么上面的问题不考虑q= 2。事实上,他们证明了:如果G是围长至少为5的平面图,M是G中的匹配,则CBCq(G,M)≤2q+1.这就是为什么他们建议研究问题1.3的以下放松。问题1.4如果G是一个围长至少为4的平面图,M是一个匹配,G,CBC q(G,M)≤ 2 q +1是真的吗?我们证明了问题1.3的一个更强的版本,即我们证明了2q+1的界对q= 3成立,并且当q≥4时,该界可以改进为2q。观察到如果M是非空的,那么2q是最好的可能,因为对于每个平面图G,非空匹配M和正整数q,我们有CBC q(G,M)≥ 2q。因此,根据我们的结果,如果q≥4,则总是相等,如果q= 3,则CBCq(G,M)等于6或7。我们还给出了一个例子,其中的上限7可以达到。因此,我们提出以下问题:问题1.5给定一个平面图G和一个非空匹配M,能否在多项式时间内判定CBC 3(G,M)= 6?在[4]中,Broersma et al. 证明了对q +1 ≤ χ(G)≤ 2 q,有BBC q(G,M)≤2 χ(G)− 2,其中M是G的匹配.这一点和CBCq(G,H)≤BBCq(G,H)+q−1的事实给出了CBC2(G,M)≤5,只要G是3-色图,M是G的匹配。但由于Grüotzs ch定理证明了无三角形平面图是3-可着色的,所以问题1.4中q = 2的情形是已知的。其他的例子都是从我们的结果得出的。利用同样的结果和外平面图是3-色的事实,我们得到:当G是外平面图且M是G的匹配时,BBC2(G,M)≤4.在这项工作中,我们证明了一个可以计算BBC2(G,M)在多项式时间,只要G是一个外平面图与匹配的骨干M。除了问题1.5之外,关于(G,M)的q-主干色数的唯一剩余问题是q= 2。Broersma等人[5]证明了BBC2(G,M)≤6,并提出问题:1)这个结果是否可以不用四元数证明56C. Araujo等人/理论计算机科学电子笔记346(2019)53⎨颜色定理?(2)能否提高到5?这两个问题仍然是开放的,虽然在[1]中给出了一些部分答案。他们通过证明如果G没有长度为4或5的诱导圈,则CBC2(G,M)≤5,如果G不含钻石,则CBC2(G,M)≤6(他们的证明都没有使用四色定理)来暗示肯定的答案。 鉴于Broersma等人提出的原始问题。[5]似乎很难,我们问下面这个简单的问题,这可能是一个很好的中间步骤,可以为他们的问题提供明确的答案问题1.6设G是一个平面C4-free图,M是G中的一个匹配. CBC 2(G,M)≤5是真的吗?最后,相对于一般的图表,M iZenskufetal. [10]给出了BBC的一个Brooks型定理的推广,即对任意图G和G中的我们在他们的证明中发现了一个错误,我们在这里介绍如何修复它。2银河骨干在这一节中,我们要证明当F是一个3-色图的星系时,CBCq(G,F)≤2q +2定理2.1若G是一个3色图,F是一个星系,则全血细胞计数q(G,F)≤ 2 q +2。证据 设c:V(G)→[3]是G的一个3-着色. 定义Li={v∈V(G)|c(v)=i和dF(v)=1},对任意v∈Li,设v为顶点,使得vv∈E(F).我们现在定义一个循环q-骨架染色CJ:V(G)→[2q+ 2]如下:(i) 如果v∈c−1(1),则cJ(v)= 1。(ii) 如果v∈c−1(2),则如果v∈L2且c(v)=1,则f ∈q+1;cJ(v)=2q + 2,当v∈L2且c(v)= 3时;(iii) 如果v∈c−1(3),则0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000CJ(v)=<$2,若v∈L3且c(v)= 2;q+ 2,否则。首先,我们证明了CJ是一个真染色.实际上,C1,C2,C3∈V(G)是由c诱导的3-划分的划分,且考虑Cij={v ∈ V(G):CJ(v)=i},对于aChi∈{1,2,C. Araujo等人/理论计算机科学电子笔记346(2019)5357q+1, q+2, q+3,2q+2}. 观察到CQJ+1,CQJ+3,C2jq+2∈C2,Cqj+2,C2j∈C3,C1=C1j.那么,CiJ是一个独立的pnt集,对于所有i∈ {1, 2,q + 1,q + 2,q + 3, 2q + 2}。这就给了我们cJ必须是一个适当的58C. Araujo等人/理论计算机科学电子笔记346(2019)53≤⊆⊆⊂⊂染色G.现在,我们证明它是一个循环的骨干染色。为此,我们证明,给定一个中心顶点v,其所有的邻居在骨干着色与适当的颜色。首先观察v接收颜色1、q+3或q+ 2。在第一种情况下,在F中它的邻居允许的颜色是q+1或q+ 2。在第二种情况下,它在F中的所有邻居都用颜色1或2着色。最后,在最后一种情况下,它在F中的所有邻居都用颜色1或2q + 2着色。因此CJ是(G,F)的循环q-骨架染色。Q3匹配主链在本节中,我们的目标是证明具有匹配骨架M的平面图G的上界。上界的证明遵循矛盾,因为我们假设存在一个最小的反例。让我们正式定义这个概念。给定一个对(G,H),(G,H)的一个子对(GJ,HJ)是一个对使得HJH和GJG.我们说(GJ,HJ)是(G,H)的真子对,如果它是(G,H)和HJH和GJG. 一对(G,H)称为(k,q)-极小的,如果CBCq(G,H)> k, 但CBCq(GJ,HJ)k是(G,H)的每一真子对(GJ,HJ)注意若CBCq(G,H)>k,则存在(G,H)的子对(GJ,HJ)是(k,q)-极小的.设Zk是一个颜色空间。一个子集S<$Zk,一个正整数q和i∈Zk,我们说颜色i对于S是q-坏的,如果S<${i−q+1,···,i+q− 1}。给定一个平面图G,我们用F(G)表示G的面集,用d(f)表示G的面集。 图G中面f的次数。现在,给定一对(G,H)和一个顶点u∈V(G),u在(G,H)中的(k,q)-全度由下式给出:不(G,H),k,q(u)= d G(u)+(2 q− 2)d H(u)。如果G,H,k,q从上下文中是清楚的,我们在符号中省略它们。引理3.1设(G,H)是一个(k,q)-极小对,其中k ≥ 2 q. 如果uv ∈ E(H),则dt(u)+dt(v)≥ 2 k + 2 q− 2。证明的草图首先,写出dt(u)=k+l和dt(v)=k+lJ。 证明了对任意u ∈ V(G),dt(u)≥ k,使得l,LJ≥ 0.设 f 是 ( G−u−v , H−u−v ) 的 循 环 q- 骨 架 k- 染 色 注 意 , af( u ) =k−(k+l−2q + 1)= 2q−(l+1),类似地af(v)= 2q−(lJ+1)。通过矛盾,假设dt(u)+dt(v)≤2k + 2q− 3。然后,我们得到:k+ l + k + lJ≤ 2 k +2 q − 3惠l + lJ≤ 2 q − 3。因此,af(v)≥2q− 1−(2q− 3−l) =l+2。然后,我们还证明了,如果S∈Zk,具有基数2q−p,其中p≥0且k≥2q,在Zk中至多有p个颜色,DC. Araujo等人/理论计算机科学电子笔记346(2019)5359对S是q-坏的。所以我们有至多l+1个颜色对于Af(u)是q-坏因此,存在一个颜色c∈Af(v),它对于Af(u)不是q-坏的,这是一个矛盾。Q下面的引理直接从欧拉公式推导而来引理3.2设G是一个平面图,M是G的一个匹配,q是一个正整数。然后,(dt(v)−2q− 2)+v∈V(G)(d(f)− 4)≤ −8。定理3.3设G是一个平面图,M是G中的一个匹配,q是一个正整数。然后又道:CBC3(G,M)≤7,且CBC q(G,M)≤ 2 q,如果q≥ 4。证明的草图首先,我们证明了当M是完美匹配且q≥4时它成立.为此,另作假设,设(G,H)为最小反例。我们采用放电法。首先给每个u∈V(G)加上电荷dt(u),给每个f∈ F(G)加上电荷d(f)−设α= 2q + 2。通过引理3.1,对于每个uv∈M,我们有:dt(u)+dt(v)≥ 2 k +2 q − 2 = 6 q − 2 = 2 α +2 q − 6。这告诉我们,匹配的每条边的电荷之和就足够了以确保每个顶点可以以非负电荷结束,在匹配的每个边缘上具有2q−6≥2的盈余。因为M是完美匹配,我们得到至少n的盈余,这显然大于三角形的数量,因此与引理3.2相矛盾。可以证明,当q= 3和k= 2q +1时,我们可以应用类似的论证。现在,假设(G,M)是一对,而M不是完美匹配。然后,我们可以对每个未被M饱和的顶点u,在G和M上添加一个悬垂顶点UJ,以获得包含(G,M)的对(GJ,MJ),并且使得MJ是GJ的完美匹配。引理由前一段和(G,M)<$(GJ,MJ)的事实得出Q定理3.3提供的两个上界都是紧的,在假设那个M。对于q≥4,若M/=n,则对于任意图,有CBC q(G,M)≥2qG. 在[8]中,他们给出了一个例子,证明存在一个平面图G3,G3的完美匹配M3使得BBC2(G3,M3)= 5。同样的例子也满足CBC3(G3,M3)=7。命题3.4 CBC 3(G3,M3)= 7。证据上界由定理3.3提供。为了证明这个下界,通过矛盾的方法,假设(G3,M3)存在一个圆的3-骨架6-染色c注意,如果uv是M3的边,则{c(u),c(v)}是{1, 4}或{2,3}。f∈F(G)60C. Araujo等人/理论计算机科学电子笔记346(2019)53一个'C'B'一D'BCFig. 1. 全血细胞计数3(G3,M3)= 7{2, 5}或{3, 6}。如果第一个案例(resp)第二,第三)发生时,我们说UV是14边(分别是,25边、36边)。在不失一般性的情况下,可以假设abJ是14边。由于d是a和bJ的邻居,d具有不同的颜色,并且不失一般性,我们可以假设aJd是25边。然后,由于c的唯一非邻居是cJ,我们推断cJd是36边。因此,由于b与aJ,d,c,dJ相邻,则bcJ必须是14边。这是一个矛盾,因为a与b相邻,cJ和c(a)∈ {1, 4}。Q4外平面图的多项式时间算法在这一节中,我们给出了一个多项式算法,给定一个外平面图G和G的一个匹配M,判定BBC(G,M)≤3。由于BBC(G,M)≤2当且仅当G是二部的且M是空的,并且因为BBC(G,M)总是至多为4,这意味着可以在多项式时间内计算BBC(G,M)定理4.1设G是n点m边连通外平面图,M ∈ E(G)是G中的一个匹配。然后,判定BBC(G,M)≤ 3可以在时间O(m + n)内完成。证据图G的树分解是一个对D =(T,{X t}t∈V(T)),使得:T是一棵根树;对于每个顶点v∈V(G),存在t∈V(T)使得v ∈ X t;对于每个边uv ∈ E(G),存在t ∈ V(T)使得{u,v}<$X t;对于每个v∈V(G),子集{t∈V(T)|v∈X t}诱导T的一个子树。如果T的顶点可以被分类为以下类型之一,则树分解是很好的(i) leaf:t是T中的一个leaf;(ii) 忘记:t有恰好一个孩子tJ,并且存在u∈V(G)使得Xt=Xt′\{u};C. Araujo等人/理论计算机科学电子笔记346(2019)5361不J(iii) 介绍: t恰好有一个子群tJ且存在u∈V(G)使得Xt=Xt′{u};并且(iv) join:t有两个孩子,t1和t2,并且Xt=Xt1=Xt2。树分解的宽度D是子集的最大大小Xt减1。图G的树宽是图G的树分解的最小宽度,记为tw(G)。已知如果G是外平面的,则tw(G)≤2,并且有一个宽度为tw(G)的树分解D=(T,{Xt}t∈V(T)),使得|时间复杂度为O(n + m)[2,7]。|= O (n) can be computed in time O (n + m)[2,7].在这里,我们使用这样的树分解来解决我们的问题。 为此,对于每个节点t∈V(T),表示为TT是T的子树,在t处被T;yVt是子集t′∈V(Tt)Xt′;by(Gt,Ht)tepair(G[Vt],H[Vt]);对于每个着色f:Xt→ {1, 2, 3},定义如下:B(f)=B(f),如果存在(Gt,Ht)的一个2-back-bone3-着色fj,使得f∈FJ;000,否则。现在,我们介绍如何计算每个Bt(f),假设值是在T的后序遍历中计算的。因此,考虑G[Xt]的一个节点t和一个3-着色f。如果t是叶子,则Bt(f)= 1当且仅当f是(G [Xt],H [Xt])的2-骨架3-着色,这可以在常数时间内测试,因为|X t| ≤ 3。因此,假设我们知道节点的每个子节点tJ的Bt′(ft. 我们根据t的类型分析所有可能的情况:(i) t是遗忘的:设 T是t的子空间,u∈V(G)使得Xt= Xt′\{u}. 观察到(Gt,Ht)=(Gt′,Ht′)。由此,我们得到:存在(Gt,Ht)的2-骨架3-染色FJ扩张f当且仅当FJ是(Gt′,Ht′)的包含f的2-骨架3-染色.因此,如果我们定义fi为f{(u,i)},对于每个i∈{1,2, 3},我们得到:Bt(f)= 1当且仅当,对某个i∈{ 1,2, 3},Bt′(fi)= 1.(ii) 设T是t的子空间,u ∈ V(G)使得Xt= Xt′ <${u}.则存在(Gt,Ht)的2-骨架3-染色f扩张f当且仅当f是(G [X t],H [X t])的2-骨架3-染色且存在(Gt′,H t′)的2-骨架3-染色fj扩张FJ= fTXt′(f限制为Xt′)。因此,我们得到:B t(f)= 1当且仅当B t′(f J)= 1。(iii) t是join:设t1,t2是t的子节点。 因为Xt将Gt1−Xt与Gt2−Xt,我们得到Gt1和Gt2的两个2-骨架3-染色在Xt上一致的并是(Gt,Ht)的一个2-骨架3-染色由此可见:Bt(f)= 1当且仅当Bt1(f)= Bt2(f)= 1。62C. Araujo等人/理论计算机科学电子笔记346(2019)53现在,观察每个步骤都可以在恒定时间内完成,因为每个Xt最多有3个可能的着色。由于T中有O(n)个节点,我们得到,一旦我们找到G的树分解,就可以在O(n)时间内计算所有值Bt(f)。当我们到达T的根r时,对于某些2-骨架3-染色,BBC(G,M)≤3的答案是f,Xr。Q我们提到,在修改和接受这个扩展摘要后,我们发现了以前证明中的一个错误。尽管如此,结果仍然是正确的,我们找到了一个更简单和更普遍的证明。注意,上面的证明可以推广到任何具有有界树宽的图G,任何固定的k,以及任何可能的骨干H。这一点,结合BBC(G,H)≤2χ(G)−1,当G是外平面图时等于5,意味着外平面图上的骨干着色问题对于每个可能的骨干H都是多项式时间可解的。5Brooks本节致力于纠正由M i Biskuf等人在[ 10 ]中证明的布鲁克类型定理的证明定理5.1设M是图G中最大度为Δ(G)的匹配。然后BBC2(G,M)≤ Δ(G)+1.为了更好地理解他们的证明,有必要定义一个特殊的结构。设x,y是连通图G中顶点v的两个不相邻的邻居,使得G−x−y是连通的。我们说:“(v;x,y)是一个叉。尽管如此,还是需要以下引理引理5.2设G是一个2连通图,G的所有顶点都是相同的度d≥ 3,除了一个特殊的顶点v是d次<。 然后,G有一个叉子(w; x,y)使得vx和vy。假设G既不是奇圈也不是完全图,他们证明了定理5.1考虑阶v1,…,v n,使得每个v i(i< n)都有一个后继的邻居。因此,他们声称G是一个正则图,M是一个完美匹配。否则,我们可以为vn选择一个度为<或者它不与M的边相关联。在这两种情况下,也将着色顶点vn。 最后,他们使用引理5.2得出G是2-连通的结论。因此,由于G既不是奇圈也不是完全图,他们使用下面的定理5.3来确保G中存在一个分叉,该分叉给出了使用至多Δ(G)+1种颜色对G的顶点着色相反,我们发现引理5.2不成立。一个简单的反例如下图所示:C. Araujo等人/理论计算机科学电子笔记346(2019)5363注意上面的图满足引理5.2的假设,但是这个图中唯一的分叉是(b;a,v)、(b;c,v)、(d;a,v)和(d;c,v),这与引理5.2相矛盾。另一方面,这个定理仍然是正确的,我们找到了一种方法来修正[10]中的演示。在介绍它之前,为了更好地理解我们的证明,我们回顾一下关于连通性的一些定义和结果定理5.3(Bryant [6])对于2-连通图,下列三个陈述是等价的:(i) G是完全图或圈;(ii) 从G中移除任意两个不相邻的顶点使其断开;(iii) 从G中移除距离为2的任意两个顶点将使其断开。注意,上面的定理声称每个不同于圈和完全图的2-连通图都包含一个分叉。图G的块是图G的无割点的极大连通子图.若G是连通的且无割点,则G是块。连通图G的块割点图是指其顶点为G的块和割点的图,且割点v与块B相邻当且仅当v∈V(B).观察G的一个块割点图是一棵树,它的所有叶子都是G的块。G的每个块是块割点图的一个叶称为leaf block。给定G的一个叶块B,如果顶点u∈V(B)不是割点,则称它是内部的.另外,如果G是1-连通的,并且G的块割点图是一条路,我们称G具有路结构。现在,我们可以证明以下内容:定理5.4设M是最大度为Δ的图G中的一个匹配。然后BBC 2(G,M)≤Δ+ 1.证据证明遵循与布鲁克斯定理相同的步骤。我们只需要在G有割点的情况下小心,因为我们可能无法将G的块的主干着色组合成G的着色。在不失一般性的情况下,我们假设G是连通的。如果G不是正则的,则可以创建阶σ = v1,., vn(G)over V(G)使得每个v64C. Araujo等人/理论计算机科学电子笔记346(2019)53具有至少一个邻居v j,其中j> i,对于每个i ∈ {1,., n− 1}和d G(v n(G))<Δ。通过在V(G)的这个排序上应用贪婪算法,所获得的着色使用最多Δ+1种颜色,因为每个顶点vj最多有Δ-1个着色邻居,并且主干M的最多一条边以vj为端点。因此,我们假设G是正则的。如果G有一个fork(z; x,y),那么我们可以产生一个阶σ =(x,y,v3,.,vn−1,z)使得每个v i至少有一个邻域v j,其中j> i,对每个i ∈{3,.,n-1},并且z有两个 不相邻的邻居,即x和y,使得当我们在G上使用贪婪算法时,使用阶σ,顶点x和y具有相同的颜色。然后,我们可以使用这个顺序,给定G中的一个匹配M,构造(G,M)的一个至多使用Δ + 1种颜色的2-主干染色。因此,我们也假设G没有分叉。如果G是完全图或圈,则上界成立(详见[10])。 因此,我们认为G是一个k-正则无叉图,G不是一个完全图,也不是一个圈。因此,注意k≥3。也要注意,由于定理5.3,G不可能是2-连通的。设B是G的一个叶块,u是G中唯一属于V(B)的割点. 情形1:κ(B-u)= 1。在这种情况下,我们声称G有一个分叉,与我们的假设相矛盾。事实上,注意u在B-u的每个叶块中都有一个邻居,而不是B-U的一个分界点。如果dB(u)≥3,设x和y是u在B-u的不同叶块中的邻居,并且不是B-u的割点。注意(u;x,y)是G的一个叉。否则dB(u)= 2,B−u的块割点树是一条路。由于G是k≥3正则的,请注意B−u中的每个叶块至少有4个顶点。如果B-u只有两个块B1和B2,则设B-u的唯一割点为z.因为只有这些块,注意z必须有两个邻居y∈V(B1)和x∈V(B2),使得y和x都不是u的邻居。 则(z;x,y)是G的一个叉。 最后,如果B-u至少有三个块,设B1是叶块,B2是与B1共享割顶点z的唯一块。再一次,一个人可以选择y∈NB1(z)使得y不是u和B2中任意顶点x的近邻(即使B2是单边),则(z;x,y)是G的一个fork.情形2:B-u是2-连通的。我们将证明u在B中恰好有两个邻居x和y,xy是唯一不属于B-u的边。接下来,我们利用这样的结构在V(G)上建立一个序,使得贪婪算法在G的2-主干染色中至多使用Δ + 1种颜色. 我们称B-u有一个分叉(z;x,y)。如果不是,根据定理5.3,B-u应该是完全图或圈。 这是不可能的,因为G是k-正则的,u在B-u中有邻居,G-V(B)。此外,定理5.3确保每两个不相邻的顶点形成一个分叉。因为G没有分叉,所以在B-u中存在分叉的唯一可能性是x和y是B-u中u的唯一邻居。因此,叶块B具有我们声称的结构:u在B中正好有两个邻居x和y,xy是唯一不属于B-u的边。最后,我们可以在V(G)上构造和排序,使得第一个顶点是B中u的邻居,然后我们有V(B)\u,x,y的所有顶点,接下来我们将V(G)\V(B)的所有顶点以这样的方式放置,即每个顶点都有一个在序列中出现较晚的邻居,并且C. Araujo等人/理论计算机科学电子笔记346(2019)5365最后一个顶点是u。观察到这样的序列上的每个顶点要么有一个在序列中出现较晚的邻居,要么是x和y的邻居,它们将被着色为相同的颜色。因此,贪婪算法最多使用Δ + 1种颜色来构建(G,M)的2-主干着色。Q引用[1] 一个RAUJO,J。,B ENEVIDES,F.,C EZAR,A.,和S ILVA,A. 循环主干着色:关于平面图的匹配和树主干。离散应用数学251(2018),69[2] BODLAENDER,H. 一个寻找小树宽的树分解的线性时间算法。SIAM Journal on Computing 25,6(1996),1305[3] 邦迪,J.,和M URTY,U. 《图论》,第1版,施普林格出版公司,2008年。[4] BROERSMA,H.,F UJISAWA,J., 马尔查尔湖, PAULUSMA,D., SALMAN,A., 和YOSHIMOTO,K. 沿两两不相交星和匹配的λ-主干着色离散数学309,18(2009),5596Combinatorics 2006,庆祝Pavol Hell 60岁生日的会议(2006年5月1日至5日)。[5] BROESMA,H.,FOMIN,F.,哥洛娃·C·H·P·A·,和WOEGINGER,G. 图的主干着色:树和路径主干。Journal of Graph Theory 55,2(2007),137[6] BRYANT,V.一些2-连通图的特征和布鲁克斯离散数学158,1(1996),279[7] CYGAN,M., FOMIN,F. 五、 科瓦利克湖, LOKSHTANOV,D., MARX,D., PILIP cZUK,M.,菲 利 普 · 朱 ,M. , 和 SAURABH , S. 参 数 化 算 法 , 第 1 版 , Springer Publishing Company ,Incorporated,2015年。[8] HAVET,F.,King,金冠草A. D、LIEDLOFF,M.,和TODIN c A,I. (圆形)主干着色:平面图中的森林主干。离散应用数学169(2014),119[9] 科瓦利克湖 快速3-着色无三角形 平面图。Micromica 58,3(Nov 2010),770[10] MIZENSKUF,J., S.KRE KOVSKI,R., 和TANcER,M. 度有界图的backbone染色。离散应用数学158,5(2010),534
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- Unity UGUI性能优化实战:UGUI_BatchDemo示例
- Java实现小游戏飞翔的小鸟教程分享
- Ant Design 4.16.8:企业级React组件库的最新更新
- Windows下MongoDB的安装教程与步骤
- 婚庆公司响应式网站模板源码下载
- 高端旅行推荐:官网模板及移动响应式网页设计
- Java基础教程:类与接口的实现与应用
- 高级版照片排版软件功能介绍与操作指南
- 精品黑色插画设计师作品展示网页模板
- 蓝色互联网科技企业Bootstrap网站模板下载
- MQTTFX 1.7.1版:Windows平台最强Mqtt客户端体验
- 黑色摄影主题响应式网站模板设计案例
- 扁平化风格商业旅游网站模板设计
- 绿色留学H5模板:科研教育机构官网解决方案
- Linux环境下EMQX安装全流程指导
- 可爱卡通儿童APP官网模板_复古绿色动画设计
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功