没有合适的资源?快使用搜索试试~ 我知道了~
可在www.sciencedirect.com在线获取理论计算机科学电子笔记346(2019)333-344www.elsevier.com/locate/entcs两个图着色对策维克托·拉赫·佩索阿1鲁迪尼·桑帕约1罗南·苏亚雷斯1DepartamentodeEstat'ısticaeMatem'aticaAplicadaUniversidadeFederaldoCear'a,Fortaleza,Brazil摘要本文回答了Bodlaender在1991年提出的一个长期悬而未决的问题:对策色数是PSPACE-硬的.我们还证明了对策Grundy数是PSPACE-困难的。事实上,我们证明了这两个问题(图着色对策和贪婪着色对策)是PSPACE-完全的,甚至如果颜色数就是色数的话尽管如此,我们证明了游戏Grundy数等于几个超类的上图的色数,扩展了Havet和朱在2013年的结果。关键词:着色对策,对策色数,贪婪着色,Grundy数,PSPACE-硬度。1介绍在图着色游戏中,给定一个图G和一组整数C,两个玩家(Alice和Bob)轮流(从Alice开始)选择一个未着色的顶点,用一个尚未分配给它的一个着色邻居的整数C着色。在贪婪着色博弈中,顶点必须被C的最小可能整数着色。如果所有顶点都成功着色,则Alice获胜。否则,鲍勃就赢了。博弈色数χg(G)和博弈Grundy数Γg(G)分别是集合C中Alice在图着色博弈和贪婪着色博弈中具有获胜策略的最少颜色数.显然,χg(G)≥χ(G)且χ(G)≤Γg(G)≤Γ(G),其中χ(G)是G的色数,Γ(G)是G的Grundy数(G的贪婪染色所能使用的最大颜色数)。1电子邮件:eurinardo@lia.ufc.br,victorlagepessoa@gmail.com,rudini@dc.ufc.br,ronan. ufc.brhttps://doi.org/10.1016/j.entcs.2019.08.0301571-0661/© 2019作者。出版社:Elsevier B.V.这是CC BY许可下的开放获取文章(http://creativecommons.org/licenses/by/4.0/)。334E. Costa等/理论计算机科学电子笔记346(2019)333图着色游戏最早是由Brams在大约38年前在着色地图的背景下考虑的,并由Gardner在1981年在他的“Mathematical Games”专栏中描述它一直没有被注意到,[2]1991年将其重新命名为博德兰德把这个问题的复杂性作为一个悬而未决的问题。用他自己的话来说,从此,图着色游戏成为一个非常活跃的研究课题。1993年,Faigle等人[8]证明了森林的χg(G)≤4,2007年,Sidorowicz[18]证明了仙人掌的χg(G)≤5。1994年,Kierstead和Trotter[13]证明了外平面图的χg(G)≤7. 1999年,Dinski和Zhu证明了:对于每一个具有无圈色数k的图,χg(G)≤k(k+ 1)[6].在2000年,Zhu证明了对于部分k-树,χg(G)≤3k + 2[20].对于平面图,Zhu[21]在2008年证明了χg(G)≤17,Sekiguchi[17]在2014年证明了χg(G)≤13,如果围长至少为4,Nakprasit等人[15]在2018年证明了χg(G)≤5,如果周长至少为7。2008年,Bohman,Frieze和Sudakov [3]研究了随机图Gn,p的χg(Gn,p)的渐近性.尽管如此,在这个问题的复杂性方面取得的进展甚微。2015年,Dunn、Larsen、Lindke、Retter和Toci[7]对此进行了调查,并用他们自己的话说,他们在森林对策色数的复杂性方面取得了部分进展。贪婪着色博弈和Grundy数博弈是由Havet和Zhu在2013年提出的。证明了在森林中的Γg(G)≤3,在部分2-树中的Γg(G)≤7。他们还提出了两个关于游戏格兰迪数的问题:• [11]中的问题5:χg(G)能被函数Γg(G)有界• [11]中的问题6:是否对任意图G都有Γg(G)≤χg(G)?在2015年,Krawczyk和Walczak[14]否定地回答了[11]中的问题5:χg(G)不被一个函数Γg(G)上界。据我们所知,[11]的问题6仍然是开放的。本文证明了即使图的色数是色数,图的着色对策和贪婪着色对策也是PSPACE-完全问题也就是说,对策色数和对策Grundy数是PSPACE-困难的。2013年,Havet和Zhu证明了对任意余图G,都有Γg(G)=χ(G)(见[11]的命题9).本文推广了这一结果,证明了对于几类已知的上图超类,如P4-稀疏图、P4-整齐图和P4-满图,Γg(G)=χ(G对于这些图类,Γ(G)可以比χ(G)大得多。此外,对于这些图类,即使Bob开始游戏并且可以通过任何回合,Alice在贪婪着色游戏中也具有具有χ(G)颜色的获胜策略。E. Costa等/理论计算机科学电子笔记346(2019)3333352游戏色数是PSPACE-hard的正如Zhu[19]所指出的,图着色游戏有了这个,我们可以定义着色游戏的两个决策问题:给定一个图G和一个整数k,• (Game着色问题1)χg(G)≤k?• (Game着色问题2)爱丽丝是否有一个获胜的策略与k种颜色?博弈着色问题1和2等价当且仅当[19]的问题1为真。在这一节中,我们证明了以下更严格的博弈着色问题3是PSPACE-完全的:给定图G及其色数χ(G),• (Game着色问题3)χg(G)=χ(G)?很容易看出,博弈着色问题1和2是博弈着色问题3的推广,因为这两个问题都等价于k=χ(G)。注意,当且仅当χg(G)=χ(G)时,χ g(G)≤k=χ(G),这是真的当且仅当Alice有一个获胜策略,k=χ(G)颜色。 那么游戏着色问题3的PSPACE-困难性意味着游戏着色问题1和2的PSPACE-困难性我们从POS-CNF问题中得到一个约化,该问题在PSPACE中是对数完备的[16]。在POS-CNF中,我们给定一个集合{X1,...,XN}和具有M个子句C1,…,C M,其中只有正变量出现(即,没有变量的否定)。两个玩家(爱丽丝和鲍勃)轮流设置一个先前未设置的变量True或False。在所有N个变量都被设置后,当且仅当公式为True时,Alice获胜。显然,由于只有正变量,我们可以假设Alice和Bob总是分别设置变量True和False我们可以假设没有一个子句包含所有变量,因为它是平凡满足的。约简的一个重要组成部分是图2的图F1,它有一个通用顶点s,两个团K(1)和K(2),都有β − 1个顶点,两个独立的集合I(1)={r1,.,r2β}和I(2)={t1,.,t2β}都有2个β顶点。对于i∈ {1, 2},I(i)的每个顶点都与K(i)中的所有顶点相邻。我们首先证明,对于2β-1种颜色,Alice在F1中获胜当且仅当她是第一个参与的人,并且在这种情况下,她必须首先给顶点s着色。引理2.1对于图1中的图F1,在2 β-1色的图着色游戏中,爱丽丝有一个获胜策略当且仅当她是第一个参与的。在这种情况下,她必须先给顶点s上色。此外,即使对手可以通过任何回合,也存在获胜策略证据不失一般性,假设爱丽丝在她的第一轮中给K(2)<$I(2)中的某个顶点着色。然后,鲍勃有一个获胜的策略,包括,在他的每一个336E. Costa等/理论计算机科学电子笔记346(2019)333∪−−(一)--F1Fig. 1.图F1. K(1)和K(2)是大小为β−1的团。顶点r1,...,r2β与K(1)的每个顶点相邻。 顶点t1, . ,t2β与K(2)的每一顶点相邻. Vertexs是universal。转,用新颜色着色I(1)如果Bob使用这个策略,在他的β回合结束时,我们有:I(1)至少有β着色的顶点,每个顶点都有不同的颜色。由于K(1)<${s}是一个团,其中β顶点与I(1)的每个顶点相邻,因此不可能用2β− 1种颜色给F1我们现在证明,对于爱丽丝来说,有一个获胜的策略,使用2β− 1颜色。在她的第一个回合中,爱丽丝用颜色1给顶点s着色。 对于随后的每个回合,Alice选择最少可用的颜色来按照以下优先级顺序对顶点进行着色:(a)K(i)的顶点,如果Bob对K(i)I(i)的顶点进行着色,(b)如果所有顶点 的一个团K(i)是着色的,她的颜色的一个未着色的顶点的另一个团,和(c)任何顶点的F1,如果所有的顶点K(1)和K(2)是着色的。在不失一般性的情况下,假设两个参与者只在K(1)I(1){s}上进行博弈。考虑K完全着色的某个轮次。请注意,在这一回合中,鲍勃最多下了β1次。 然后,他们在K(1)s中使用β颜色,在I(1)中使用至多β1颜色。由于I(1)中的每个顶点都可以与I(1)中的任何顶点共享相同的颜色,因此它们最多使用了β+β1种颜色,并且I(1)中所有未着色的顶点都可以用I(1)中已经使用的任何颜色着色。Q定理2.2给定一个图G,判定χ g(G)= χ(G)是否PSPACE-完全. 因此,如果k是一个整数,决定χ g(G)≤ k或决定Alice是否有k种颜色的获胜策略是PSPACE完全问题。证据[草图]不难看出,这三个决策问题都在PSPACE中。给定具有N个变量X1,.,的POS-CNF公式,X N和M条款C1, . ,CM,letpj(对于j=1, . , M)是子句Cj的大小,并且令q i(对于i =1,.,N)是包含变量X i 的 子 句 的 数 目。设p=maxj=1,...,M{pj}和q=maxi=1,...,N{qi}。 也就是说,每个子句 最多有p个变量,每个变量最多出现在q个子句中。 设β = max {p,q,4 N}+2。我们将构造一个图G,使得χ(G)= 2 β − 1和χ g(G)= 2 β − 1当且仅当Alice对于POS-CNF公式有一个获胜策略。最初,所构造的图G是图1的图F1给G加一个新的顶点y。对于每个变量xi,在G中创建一个顶点xi。对于每个子句Cj,我们将为其创建一个子句团。首先创建一个顶点为lj,1,.的团,l j,pj,并且用边将l j,k连接到x i当且仅当两者都关联到相同的变量,对于k=1, . ,pj. 还可以定义新的顶点lj,0(其中h不与顶点y相关联),并将其用边连接到顶点y。对于每个顶点lj,k(j = 1,.,M和k=0, . ,p,j),将其替换为两个真实的顶点lj,j,k和lj,J,k,其中lj,j,k是具有lj,k的相同邻域的n个顶点。此外,在C j的子句团中添加一个大小为2(β−pj)−3≥4N的团Lj,并将L j的所有顶点连接 到s。有了这个,r1r2.r2βt1t2. ......你好。t2βK(1)s(2)E. Costa等/理论计算机科学电子笔记346(2019)333337′∨ ∧ ∨ ∧ ∨ ∧∨r1r2.r2βt1t2. ......你好。t2βF1K(1)s(2)yL1L1,0L2L2,0L3l3,0L4L4,0l1, 1l 1,2l2, 1l 2,2l3, 1l 3,2l4, 1l 4,2X1X2X3X4图二.构造图G的公式为(X1X2)(X1X3)(X2X4)(X3X4). 回想一下,每个顶点lj,k表示两个真值-t赢得lj,k和l′j′,k;L1,L2,L3,L4是具有29个顶点的团。 Bob在图形着色游戏中有一个35种颜色的获胜策略。所有子句团都有2个β− 1顶点。图2显示了公式(X1<$X2)<$(X1<$X3)<$(X2<$X4)<$(X3<$X4)的构造图G请注意,Bob有一个获胜策略:如果Alice设置X1True,Bob设置X4False;如果Alice设置X4True,Bob设置X1False;如果Alice设置X2True,Bob设置X3为假;如果Alice设置X3为真,Bob设置X2为假。在这个例子的约简中,我们有N= 4个变量,M= 4个子句,p= 2,q= 2,β= 4N +2 = 18,集团L1到LM每个有2(β−p)−3 = 29个顶点很容易证明χ(G)= 2 β − 1。 用颜色1给s着色,给顶点y和每个顶点xi(i =1,...,n),颜色为2 β−1。F1的每个团的顶点可以用颜色2到β着色,并且F1的每个独立集合可以用颜色β+1着色。 对于每个j = 1,...,M,用颜色2k+ 1和2k+ 2(k=0, . ,pj)。最后,用下式给团Lj的顶点着色:颜色2pj+3, . . . ,2β−1。由于表示子句的团包含2β−1个顶点,则χ(G)= 2β− 1。接下来,我们证明Alice在图着色博弈中有获胜策略当且仅当她在POS-CNF中有获胜策略根据引理2.1,在她的第一步中,Alice必须给F1的顶点s着色,因为否则F1不能用2β− 1色。还 请注意,所有可变顶点的度最多为2 q <2 β − 1,然后总是可以用{1,.,2β−1}。我们证明了顶点y在前三圈中是着色的。 这样,子句团的每个顶点都有2 β−1的精确度。为了使用{1,.,2β−1},爱丽丝必须保证出现在小句团外部邻居中的所有颜色也出现在小句团内部。另一方面,我们表明,鲍勃我们首先证明,如果鲍勃在POS-CNF博弈中有获胜策略,那么χg(G)>2β− 1。假设Bob在POS-CNF游戏中获胜,Alice开始338E. Costa等/理论计算机科学电子笔记346(2019)333用颜色1给s着色(回想引理2.1)。鲍勃可以使用以下策略。在他的第一轮中,他用颜色1给y着色,然后在随后的每一轮中:如果Alice对某个i给N[xi](xi的闭邻域)中的一个顶点着色,Bob认为她在POS-CNF博弈中标记了Xi为真,并用颜色1给代表他在获胜的POS-CNF策略中选择的文字Xj的顶点xj着色;如果Alice对于某个i不对N[xi]中的任何顶点着色,那么Bob就像Alice 已经超过了她在POS-CNF游戏中的回合。由于Bob在POS-CNF博弈中有一个获胜的策略,在某个时候,某个子句的所有文字都将被标记为false。这意味着在某个子句集团之外的所有邻居都将被着色1. 由于团有2个β−1顶点,颜色1不能使用,我们有,χg(G)>2β− 1。我们现在证明,如果爱丽丝在POS-CNF博弈中有一个获胜策略,那么χg(G)=2β− 1。假设Alice在POS-CNF游戏中获胜,她将F1的顶点s着色(颜色为1)。首先,假设鲍勃在第一轮中没有用颜色1给y着色。然后,在下一轮中,Alice可以保证y接收到不同于1的颜色。在此之后,她总是可以用颜色1(例如,lJi,0,lJiJ,0或其他)为任何子句集团内的顶点由于每个团L j至少有4个N顶点,那么Alice也可以对所有可变顶点进行着色,并保证所有可变顶点的颜色都出现在L j中。因此,假设Bob用颜色1给顶点y着色。有了这个,Alice可以使用以下策略来玩:(1)如果Bob在F1的顶点上玩,那么她在F1中使用她的获胜策略来玩引理2.1;(2)如果Bob在从顶点li,j获得的某个孪生上玩,那么Alice在另一个孪生中使用最少可用的颜色;(3)如果Bob在某个Lj上玩,那么Alice玩得好像Bob已经通过了POS-CNF游戏的轮到,这意味着她选择顶点xj并且用不同于1的颜色来着色它,其中Xj是她在POS-CNF游戏中的获胜策略所选择的文字(4)如果Bob在xi上下棋,那么Alice就像Bob在POS-CNF游戏中选择了Xi为假一样下棋;(5)如果其他移动是不可能的,那么Alice选择G的任何顶点,并用最少的可用颜色对其着色通过这种策略,当POS-CNF博弈结束时,每个子句团都有一些颜色不同于1的外部邻居或一个着色的顶点1. 有了这个,Alice和Bob可以使用颜色1,..., 2 β − 1,因为Alice可以保证每个有2 β − 1个顶点的团接收其外部邻居的所有颜色(再次回忆每个团L j至少有4 N个顶点)Q3游戏Grundy数是PSPACE硬对于博弈Grundy数也可以得到类似的结果。与博弈着色问题不同,贪婪博弈着色问题满足以下条件:命题3.1如果爱丽丝在贪婪博弈着色问题中有一个k种颜色的获胜策略,那么爱丽丝也有一个k +1种颜色的获胜策略。E. Costa等/理论计算机科学电子笔记346(2019)333339F2图三. 图F2:有3种颜色,第一个移动的人赢得贪婪游戏因此,我们可以定义贪婪着色游戏的决策问题:给定一个图G和一个整数k,• (贪婪对策染色问题1)Γg(G)≤k?也就是说,爱丽丝在贪婪着色游戏中是否有使用k种颜色的获胜策略在这一节中,我们证明了下面的更严格的贪婪博弈着色问题2是PSPACE-完全的:给定图G及其色数χ(G),• (贪婪博弈着色问题2)Γg(G)=χ(G)?也就是说,在贪婪着色博弈中,爱丽丝是否有使用χ(G)颜色的获胜策略很容易看出,贪婪博弈着色问题1是贪婪博弈着色问题2的推广(只需设置k=χ(G))。然后,贪婪博弈着色问题2的PSPACE-困难性蕴涵了贪婪博弈着色问题1的PSPACE-困难性我们从POS-CNF问题中得到了一个非常相似的约化(如第2节所示的博弈着色问题)。减少的一个重要因素是图3的图F2。我们首先证明,在3种颜色的情况下,Alice在F2中赢得比赛,当且仅当她是第一个参加比赛的人,在这种情况下,她必须首先给顶点S着色。引理3.2对于图3中的图F2,爱丽丝在3种颜色的贪婪着色游戏中有一个获胜策略当且仅当她是第一个玩的。在这种情况下,她必须先给顶点s上色。证据 假设爱丽丝是第一个参与游戏的人,并且第一个给顶点r着色(贪婪游戏中的颜色为1)。然后Bob可以给顶点t2着色(颜色1)。这样,s和t就不能被着色为1,然后鲍勃可以在下一轮中通过着色两个黑色顶点中的一个(颜色1)来强制t1或t3现在假设爱丽丝是第一个玩的,并先给顶点s着色(颜色1)。因此,在贪婪博弈着色中,{r1,r2,r3,t1,t2,t3}因此,{r1,r2,r3,t1,t2,t3}中的所有顶点都可以用2或3着色。此外,爱丽丝可以在她的第二和第三回合中使用赢得游戏的颜色{2, 3}为r和t最后,假设鲍勃是第一个上场的。他可以通过先给顶点r2着色(颜色1)来赢得游戏。 在他的下一轮,他可以颜色的黑色邻居的r1或r3(颜色1)。有了这个,r1或r3将被着色为4,鲍勃赢得了比赛。Q定理3.3给定一个图G,判定Γ g(G)= χ(G)是否PSPACE-完全. 因此,如果k是一个整数,判定Γ g(G)≤k是否是一个r1r 2r 3t1t2t3RS不340E. Costa等/理论计算机科学电子笔记346(2019)333′∨ ∧ ∨ ∧ ∨ ∧∨r1r 2r 3t1t2t3yF2JL0RS不yL1L1,0L2L2,0L3l3,0L4L4,0l1, 1l 1,2l2, 1l 2,2l3, 1l 3,2l4, 1l 4,2X1X2X3X4X1X2X3X4见图4。构造图G的公式为(X1X2)(X1X3)(X2X4)(X3X4). 回想一下,eachvertexlj,k表示两个真-t赢得lj,k和l′j′,k,L0是具有32个顶点的团,而L1,L2,L3,L4是具有29个顶点的团。鲍勃在贪婪着色游戏中有一个35种颜色的获胜策略PSPACE完全问题。证据[草图]我们将遵循定理2.2的几乎相同的简化(从POS-CNF),包括每个顶点xi的度为1的邻居xi,并将图F1替换为图F2,其中所有顶点都与具有2β−4个顶点的新团L0相邻。同样,在这种情况下,我们知道Lj是一个有2(β−pj)−3个顶点的团,其中1 ≤j≤M。图3显示了相同公式(X1<$X2)<$(X1<$X3)<$(X2<$X4)<$(X3<$X4)的构造图G在这个例子的约简中,我们有相同的值N= 4个变量,M=4个子句,p= 2,q= 2,β= 4N + 2 = 18,团L0有2β− 4 = 32个顶点,团L1到LM各有2(β−p)−3 = 29个顶点。如定理2.2所示,χ(G)= 2β− 1。使用类似的论点,在证明定理2.2,我们得到了结果。主要的区别是,而不是用不同于1的颜色着色顶点xi,Alice应该用颜色着色顶点xi1.Q4少P4图的对策Grundy数如在引言中所提到的,Havet和Zhu在2013年证明了对于任何上图,Γg(G)=χ(G)(见[11]的命题9),因为在上图中χ(G)= Γ(G在这一节中,我们证明了对于已知的上图的超类,如P4-稀疏图,P4-整齐图和P4-满图,这也会发生,使得Γ(G)可以任意地大于χ(G).上图是没有导出P4的图.一个图G是P4-稀疏的,如果G中的每一个五点集至多诱导一个P4[12]。P4-稀疏图在联合、连接和蜘蛛方面有很好的结构分解。给定图G1=(V1,E1)和G2=(V2,E2),G1和G2的并为图G1<$G2=(V1<$V2,E1<$E2),G1和G2的并为图G1<$G2=(V1<$V2,E1<$E2<${uv:u∈E. Costa等/理论计算机科学电子笔记346(2019)333341P4-可伸展P4-整洁P4负载扩展P4-稀疏P4-lite扩展P4负载P4-可约Cograph图五、 具有少量P4的图的层次.V1,v∈V2})。一个蜘蛛是一个图,它的顶点集有一个分区(R,C,S),其中C={c1,...,c k}且S ={s1,...,sk}(k≥ 2)分别是团集和稳定集; si与cj相邻当且仅当i= j(细蜘蛛),或si与cj相邻到cj当且仅当i/=j(一个粗蜘蛛);并且R的每个顶点都与C的每个顶点相邻,而与S的每个顶点不相邻。请注意,细蜘蛛的补集是粗蜘蛛,反之亦然。Jamison和Olariu[12]证明了,如果图G是P4-稀疏图,则G是两个P4-稀疏图的不交并或并,或G是一个蜘蛛(R,C,S),使得G[R]是一个P4-稀疏图,或G至多有一个顶点.作为一个例子,下面的P4-稀疏图序列(Gk)满足Γg(Gk)=χ(Gk)=2k和Γ(Gk)= 3k. 设G1为P4a1b1c1d1. 对于k≥2,设Gk由Gk−1与P4ak bk ck dk的并得到。显然,χ(G k)= 2 k:颜色ai和ci具有颜色2i−1,并且颜色dcolorbi和di具有颜色2i,对于每个1≤i≤k。更进一步,Γ(Gk) =3k:颜色ai和di分 别 对应颜色3i−2,颜色dcorbi和ci分 别 对应颜色3 i − 1和3 i。最后,Γ g(G k)= 2 k:Alice总是可以避免P4aibicidi的第二个端点a i和di接收到相同的颜色。我们称一个图是扩充的P4-负载图,如果每一个至多有6个顶点且包含两个以上诱导P4的这个图类在[10]中被引入,并且开发扩展P4负载图的算法的动机在于这样一个事实,即它们位于广泛研究的包含许多具有很少P4的因此,以有效的方式解决扩展P4-负载图的有趣问题,立即意味着所有这些类的有效的,通用的算法。另一个动机是扩展的P4-负载图不包含在完美图中;因此这项工作获得了与完美无关的着色结果。最近有一些文章讨论了扩展P4-满图的着色问题.例如,在Grundy数[1]和共色数[4]中。Giakoumakis[10]利用伪分裂图和拟蜘蛛图证明了扩展P4-满图的一个重要结构刻画.给定一个点集划分为(C,S)的分裂图G,其中C是团,S是广义P4-可约P4稀疏342E. Costa等/理论计算机科学电子笔记346(2019)333独立集,我们说G是原始,如果S中的每个顶点在C中有一个非近邻,且C中的每个顶点在S中有一个近邻。我们称一个图G是伪分裂的,如果它的顶点集有一个划分(R,C,S),使得S导出一个独立集,C导出一个团,C_S导出一个原始分裂图,并且R的每个顶点都与C的每个顶点相邻而与S的每个顶点不相邻.请注意,伪分裂的补图也是伪分裂图,蜘蛛图也是伪分裂图。一个拟蜘蛛是从一个蜘蛛(R,C,S)中得到的一个图,其中最多有一个来自CS的顶点被K2或K2所取代(保持邻域)。显然,每一只蜘蛛都是准蜘蛛。定理4.1([10])一个图G是扩张的P4-负载的当且仅当下列条件之一(a) G是两个非空扩展P4-满图的不交并或并.(b) G是一个拟蜘蛛图或伪分裂图(R,C,S),使得G[R]是一个扩张图P4-负载图。(c) G同构于C5,P5,P5,或至多有一个顶点.为了确定扩展的P4-满图的Γg(G),我们引入参数Γjg(G):在贪婪着色博弈中,即使Bob可以开始博弈,也可以通过任何回合(即在回合中不着色顶点),Alice仍有获胜策略的最小颜色数.注意,Γg(G)≤Γjg(G)。我们证明了对于扩展的P4-满图,Γjg(G)=χ(G),这意味着在这类图中,Γg(G)=χ(G在下文中,我们获得了联合和连接操作的上界。引理4.2给定图G1和G2,• Γjg(G1<$G2)≤Γjg(G1)+ Γjg(G2)且• Γ jg(G1<$G2)≤ max {Γjg(G1),Γ jg(G2)}.证据[示意图]爱丽丝只需要在鲍勃按照她的最佳策略在这个图中玩的同一个图中玩。如果没有未着色的顶点,Alice就给另一个图中的一个顶点着色(在这种情况下,她认为Bob在这个图中通过了他的回合)。Q引理4.3若G是拟蜘蛛图或伪分裂图(R,C,S),则ΓJg(G)=χ(G)。 若G同构于C5,P5或P5,则G有Γ jg(G)= χ(G).证据【略】有些案例需要分析,限于篇幅,就不赘述了。在大多数情况下,Alice只需避免Bob将独立集合S的所有顶点着色为颜色1。Q由此得到了扩展P4-满图的主要定理定理4.4若G是一个扩展的P4-负载图,则G的Γ g(G)= Γ jg(G)= χ(G),它可以在线性时间内计算. 也就是说,在扩展的P4-满图中,即使Bob开始了着色游戏,Alice也能赢得具有χ(G)颜色的贪婪着色游戏,并且也能通过任何回合.E. Costa等/理论计算机科学电子笔记346(2019)333343证 据 [ 略 ] 由 定理4.1 和 引理4.2 、 4.3 归 纳得 出,因 为对 于任 意图 G1 和 G2 , χ(G1<$G2)= χ(G1)+ χ(G2)且χ(G1<$G2)= max {χ(G1),χ(G2)}。Q5最后发言本文在定理2.2和3.3中证明了:给定图G和整数k,判定χg(G)≤k或Γg(G)≤k是PSPACE-完全问题。在定理2.2和3.3的证明中,在约简中得到的k值(即k=χ(G))可以很高。在连通图G中仅考虑k= 2色的情况下,已知χg(G)≤2当且仅当G是星K1,n.对于贪婪着色博弈,我们有以下刻画:引理5.1一个连通图G有Γ g(G)= 2当且仅当G是二分图,其顶点的邻域是二分图的一部分。证据若Γg(G)= 2,则G必是二部的,因为χ(G)≤Γg(G)= 2. 此外,若G不是二部的,则G的正则性定理有:Γg(G)≥χ(G)>2.然后假设G是二分的,具有二分性(A,B)。不失一般性,设G有A的一个顶点v,它的邻域是B.如果爱丽丝在第一轮给v着色(颜色1),那么B的顶点都不能着色为1,因此A的所有顶点都将着色为1。 因此,B的所有顶点都着色为2。现在假设A的每个顶点在B中都有一个非邻居,B的每个顶点在A中都有一个非邻居。假设w是Alice着色的第一个顶点。不失一般性地假设w∈A。 因为G是连通的,所以W有 B中距离为3的非邻居z(即w和z是P4的端点)。因此,在第一轮给z着色(颜色1),Bob在这个P4中强制3种颜色。Q然而,对于k= 3种颜色,贪婪游戏着色的复杂性是未知的。猜想5.2判定Grundy数Γ g(G)≤ 3是否PSPACE-完全确认本研究得到了Funcap [4543945/2016] Pronem、CNPq[425297/2016-0] Universal和CAPES [88887.143992/2017-00] DAAD Probral的支持引用[1] 你好,J。 和C. Linhares-Sales,关于grundynumberofgraphswithfewP42514[2] Bodlaender,H. L., 关于一些着色游戏的复杂性,Int J Found Comput Sci2(1991),pp. 133-344E. Costa等/理论计算机科学电子笔记346(2019)333[3] Bohman,T.,A. Frieze和B. Sudakov,随机图的博弈色数,随机结构算法32(2008),pp. 223-235[4] 布拉沃河美国,S. 克莱因湖T. Nogueira ,F. Protti和R. M. Sampaio,Partitioningextend edP4-ladengraphs into clues and stable sets,Information Processing Letters 112(2012),pp. 829[5] Corneil,D.,H. Lerchs和L. Burlingham,补可约图,离散应用数学3(1981),pp. 163[6] 丁斯基,T.和X.朱,图的对策色数的一个界,离散数学,196(1999),pp. 109[7] Dunn,C.,V. Larsen,K. Lindke,T. Retter和D. Toci,树和森林的游戏色数,离散数学理论计算机科学卷。17 no.2(2015)。[8] 法伊格尔大学,联合Kern,H.A. Kierstead和W.T. Trotter,关于几类图的对策色数,ArsCombinatoria35(1993),pp.143[9] 加德纳,M.,数学游戏,Scienti fic American244(1981),pp.18[10] Gia k oumakis,V.,P4-loadedgraphs:一类新的脆性graphs,信息处理快报60(1996),pp. 29[11] Havet,F.和X.Zhu,The game grundy number of graphs,Journal of Combinatorial Optimization25(2013),pp. 752-765。[12] 贾米森湾和S.张文,等.离散应用数学.北京:清华大学出版社,200135(1992),pp. 115[13] Kierstead,H. A.和W. T. Trotter,Planar graph coloring with an uncooperative partner,Journal ofGraph Theory18(1994),pp. 569-584.[14] 克劳奇克,T.和B. Walczak,不可比图上的非对称着色游戏,离散数学电子笔记49(2015),pp.803-[15] Nakprasit,K.M. 和K.Nakprasit,具有特定围长的平面图的游戏着色数,图形和组合学34(2018),pp。349-354.[16] Schaefer,T.J.,关于某些两人完全信息博弈的复杂性,计算机与系统科学杂志16(1978),pp.185[17] Sekiguchi,Y.,给定围长的平面图的对策色数,离散数学330(2014),pp. 11[18] Sidorowicz,E.,仙人掌的游戏色数和游戏色数,信息处理快报102(2007),pp。147[19] Zhu,X.,平面图的对策着色数,组合理论杂志,B75(1999),pp. 245[20] Zhu,X.,伪部分k树的博弈色数,离散数学215(2000),pp.245–[21] Zhu,X.,Refined activation strategy for the marking game,Journal of Combinatorial Theory,SeriesB98(2008),pp. 1
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功