圈图幂的全染色问题及其特性

nnn≥≥nn[2014-05-23]−≤ [001]≥≥可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）747-758www.elsevier.com/locate/entcs多点圈的偶次幂是1型全染色的Alesom Zorzi2塞丽娜·德·菲格雷多3COPPE/UFRJ里约热内卢-RJ，巴西拉斐尔·马查多4PPGMQ-InmetroDuque de Caxias- RJ，巴西PPCIC-CEFET/RJ里约热内卢-RJ，巴西你是威尔顿·S。Souza5IC/UFFNiter'oi-RJ，Brazil摘要圈幂图Ck是由无弦圈Cn通过在距离至多为k的任意一对顶点之间添加一条边而得到的图。 循环图的幂已经在文献中被广泛研究，特别是关于着色问题，顶点着色和边着色问题都在课堂上得到了解决。然而，全染色问题仍然是开放的权力循环图。 一个图G是1型的，如果它能被Δ（G）+1色全着色，如果它不能被Δ（G） +1色全着色，则它是2型的。Δ（G）+ 1，并且可以用Δ（G）+ 2着色，其中Δ（G）表示G中顶点的最大度。虽然Campos和de Mello[4]以及Almeida等人[1]的近期工作对n和k的特定值给出了部分结果，但全染色问题远未在该类中得到解决。一个显著Campos和de Mello的猜想[4]指出，Ck，2k n/2是类型2，当且仅当n是奇数，n = <3（k + 1）。特别是，该猜想意味着，对于每个k2 、号码是有限的，且n =3（k+ 1）的圈图Ck 讨论了Campos和de Mello关于圈图幂的猜想，并证明了关于圈图的even-pow-er猜想的一个较弱的版本：everyCkwithevenk2andn4k2+2k等于Type 1。我们证明实际上更强，并表明，对于每个偶数k n/2，循环的2型幂的数量图Ck至多为2k2K. 因此，我们的结果为Cam pos猜想和de Mello猜想关于圈图幂的成立提供了有力的证据.关键词：图论，图算法，全染色，圈图的幂1由巴西机构CNPq和FAPERJ部分支助的研究2电子邮件：alesom@cos.ufrj.br3电子邮件：celina@cos.ufrj.br4电子邮件：rcmachado@inmetro.gov.br5电子邮件：ueverton@ic.uff.brhttps://doi.org/10.1016/j.entcs.2019.08.0651571-0661/© 2019作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。748A. Zorzi et al. /Electronic Notes in Theoretical Computer Science 346（2019）747nnnKn2k+12k+22k+32k+42k+52k+62k+7...奇数n 3（k+1）r（2k+1）r（2k+1）+k...偶数η奇数n ≥ 3（k+1）2Δ+1Δ+1Δ+2Δ+1Δ+1Δ+1Δ+1...CΔ+1Δ+1...Δ+1Δ+13Δ+1Δ+1Δ+2Δ+1Δ+2Δ+1Δ+1...CΔ+1Δ+1...Δ+1Δ+14Δ+1Δ+1Δ+2Δ+1Δ+2Δ+1Δ+1...CΔ+1Δ+1...Δ+1Δ+15Δ+1Δ+1Δ+2TCCΔ+2TCCO...CΔ+1TCC...TCCO6Δ+1Δ+1Δ+2TCCΔ+2TCCO...CΔ+1TCC...TCCO.............................................KΔ+1Δ+1Δ+2TCCΔ+2TCCO...CΔ+1TCC...TCCOFig. 1. 本文综述了图C_k中的两个问题（TCC和全染色）的研究现状。 的行该表表示参数k，列表示作为k的函数的参数n。条目Δ + 1表示1型图; Δ + 2表示2型图; TCC表示TCC已被证明，但1型和2型之间的分类未知; C表示由于符合条件而不是1型的图。在已经有另一个标签的条目中省略标签C，但是具有奇数n和2k+10时，Ck的TCC.注意，这个结果也证明了对于奇数n的某些特定值的TCC。图Ck（n=r（2k+1）且r>0）是1型图，这是由[3]得到的.1介绍全色数χT（G）是对图G的顶点和边着色所需的最少颜色数，使得没有入射或相邻元素（顶点和边）接收相同的颜色。Behzad [2]和Vizing[14]分别提出了著名的全着色猜想（TCC），对任意简单图G，χT（G）≤Δ（G）+2，其中Δ（G）为最大值图的顶点的度。TCC已解决限制图形族-Les，如完全r-部图、分裂图、对偶弦图和具有高最大度的图。然而，一般图的TCC已经开放了50多年，并且在仅限于弦图和循环图的幂时仍然开放。我们称函数C：E（G）<$V（G）→ [t]为全染色，其中[t] ={0，.，t}，相邻元素必须接收不同的颜色。顶点vi的颜色表示为类似地，边vi vj的颜色由C（vi vj）表示。很容易看出，没有一个图可以用少于Δ（G）+1个颜色完全着色，这意味着全色数χT（G）≥Δ（G）+1的一个下界如果图G能被Δ（G）+1色完全着色的称为Type 1，如果不能被Δ（G）+1色完全着色的称为Type 1，用Δ（G）+1色着色，但可以用Δ（G）+2色着色，称为2. San'nchez-Arroy[12]证明了确定全色数的全色问题是NP-困难的.重要的是要注意，在类中TCC的有效性和复杂性之间不存在全着色问题的解决方案例如，对于二部图，TCC被解决，但是全着色问题是NP-困难的[12]。另一方面，对于树宽有界的图，其全染色问题是多项式的，而TCC不是多项式的”[8]这是一个比喻。边染色与全染色有很强的相似性著名的Vizing定理将边着色分类问题分为第一类（具有Δ颜色的边可着色图）和第二类（具有Δ+1颜色的边可注意，边着色和全着色问题都是A. Zorzi et al. /Electronic Notes in Theoretical Computer Science 346（2019）747749nnnnnnnnnNP-完全。特别地，通过从边着色的还原，全着色问题首次被证明是NP-困难的[12];这可能表明全着色将是一个更难的问题，然而，我们知道类的边染色是NP-困难的，但全染色是多项式[9]。由于边染色和全染色都是NP-完全问题，因此在定义“easy” sufficient or necessary conditions for a graph to be Class 1 or Type 1, and下面讨论其中的两个条件。边着色的过满条件是指边的个数大于Δ[n/2]，是图为2类的充分条件，图为1类的充分条件是非过满的.例如，任何具有奇数n的正则图都是过满的，因此是2类。利用过满条件，对圈图和完全图的基本类进行了边着色的完全分类。全染色的一致性对于正则图，当该差异为零时，一致性条件要求每个颜色类具有与图的阶相同的奇偶性[5]。一 功率 的 周期 图表，表示 通过 Ck，是 一 图 哪里 V（Ck）=n n{v0，v1，...，v n-1}，其中v0，v1，.，v n−1是一个生成圈，E（C k）= E1<$···Ek，其中Ei={v j v（j + i）|0 ≤j≤n−1}。在本文中，当我们提到一个顶点v i∈ V（C k）时，我们指的是v imodn。 圈的幂是一类研究得很好的图，它涉及到着色问题的几种变化。 顶点着色问题可以在类中用贪婪算法解决[3]，边着色问题可以使用过满条件解决[10]。通过定义，圈图的幂Ck推广了圈图Cn=C1n n以及完全图Kn=Ck，其中hk≥[n/2]. 的基本类图是完全分类关于全染色通过使用符合条件：1型完全图Kn恰好是一致图，即，图Kn，其中nmod 2 = 1。然而，一致性条件并不表征类型1圈图，因为存在类型2的一致圈图，例如图C7。对于n和k的特定值，有关于循环图Ck的幂的TCC和全染色问题的结果。图1总结了这些结果，第一列n= 2k + 1表示类型1完全图，因为n是奇数。 如果n是奇数且2k+ 12k+ 1，则Ck如果n= 7，则为类型2，否则为类型1[3];如果k= 3，n>2k + 1，则如果n= 9或n= 11，则Ck为类型2，否则为类型1;如果k= 4且n >2k +1，则如果n= 11或n= 13，则Ck为类型2，否则为类型1[1]。最后两个结果于2014年在第六届拉丁美洲图形派系研讨会上发表，并发表在会议摘要集上（与 没有详细的证据）。 若n是偶数且n >2k+1或n=r（2k+ 1）+k且为整数r >0，则证明了这类Ck图的TCC[4]：若n=r（2k+1），其中n为整数750A. Zorzi et al. /Electronic Notes in Theoretical Computer Science 346（2019）747nnnKnnn2n1n2n1nnn2nn1n2n1n2nn1n1n2n2nn1r >0，则Ck是类型1。这个结果特别有趣，因为它是de Figueiredo，Meidanis和deMello [6]的拉回算法和Golumbic[7]的非常贪婪邻域着色（V GNC）算法的推论。文[3]证明了如果环图C k的一个p-型，其中h为2n-1，则n为n3奇数，则χ T（G）= Δ +2。否则，χ T（G）= Δ +1。对猜想1.1给出了一个强有力的证明：证明了圈图Ck，其中n≥4k2+2k的每一个偶幂都是Type 1.此外，我们还证明了，对于每个偶数k[n/2]，圈图Ck的Type2p的个数至多为2k2−k，by<显示在所考虑的范围内的每一个其他图的类型1全染色。我们还证明了，对于任何固定的k≥2，如果n大于函数f（k），我们可以将一个图C k分解为两个图C k和Ck，其中n=n1+n2，nn1n2一种基于分解的多项式时间全着色循环幂算法图CkCk运用同样的推理对于CkCk如果n1> f（k）或n2> f（k）.本文的结构如下。在第2节中，我们定义了第3节中使用的运算和算子，以表示循环图的偶次幂为类型1的阈值。在第4节中，我们提出了一个框架，分解成一组更小的循环图的幂循环图。在第5节中，我们提出了我们的结论和可能的进一步发展方向和应用程序的开发工具。2兼容性和自下而上的组合在本节中，我们定义了两个操作，作为构造图Ck的第1类全染色，来自另外两个第1类图Ck和Ck，n使得n1+n2=n。n1n2一 功率 的 路径 图表，表示 通过 Pk，是 一 图 哪里 V（Pk）=n n{v0，v1，...，v n-1}，其中v0，v1，.，v n−1是一条生成路径，E（P k）= E1···Ek，其中Ei={v j v（j + i）|0 ≤ j ≤ n − 1}。 在路图的幂v j+ i中，模块化操作。我们的目标是将一个圈图的幂分解为两个路图的幂K 和Pk，其中n1+n2=n，以及两组边N−（wx）N+（wx−1）和N−（wy）N+（wy−1），其中wx，wy∈V（Ck），以这种方式，我们可以使用图Ck和Ck分别完全着色Pk和Pk，使用E（Ck）\E（Pk）和E（Ck）\E（Pk）的边的颜色，以对边着色N−（wx）N+（wx−1）和N−（wy）N+（wy−1）的一个有效的总颜色。转移全着色的操作被称为拉回，它由de Figueiredo，Meidanis和de Mello定义 [6]。从G到GJ的拉回是一个函数f：V（G）→V（GJ），使得：（i）f是同态，即， 若pq∈E（G），则CPA. Zorzi et al. /Electronic Notes in Theoretical Computer Science 346（2019）747751810nn1n1n2n2n≥n18n10n1nn2n1nn2n(a)（b）第（1）款图二、一个合成过程的例子，注意顶点wx∈Ck表示顶点vi∈Ck而顶点wy∈Ck表示顶点uj∈Ck。 （a）图Ck，其中hn=18，k=3. Ther ed虚线边表示集合N−（wx）N+（wx−1）和N−（wy）N+（wy−1）。 （b）顶点vi表示图P3的第一个顶点，顶点uj表示图P3的第一个顶点. THE10 8集合N−（wx）N+（wx−1）和N−（wy）N+（wy−1）w的边被省略以提高图P3和P3，但在2a中可以看到集合。f（p）f（q）∈E（GJ）：（ii）f在限制于N（p）时是内射的，其中N（p）表示p的开邻域，p∈V（G）.回调是一个强大的工具，它允许我们将着色从一个图转移到另一个图。我们在定义2.1和2.2中更正式地定义了这个过程的运算和算子。定义2.1我们说，一个循环的幂的路径分解的k-幂图Ck是分解成两个路径图Pk和Pk的幂，以及两个nn1n2边N−（wx）N+（wx−1）和N−（wy）N+（wy−1）的集合，距离在wx，wy∈Ck在生成圈中大于2k.wx表示顶点vi∈Pk，它是Pk的诱导路的第一个顶点，wy表示顶点uj∈Pk，它是Pk的导出路的第一个顶点.注意n为4k+2的圈图Ck的每一个幂都有一个k-幂路分解.图2说明了C3的路径分解的3次幂.图Ck的顶点的半割是V（G）中k个连续顶点的集合，考虑到循环序.我们表示顶点的两个特殊半割：N−（wx）={w q|x − k ≤ q 2。请注意，这种交换不会改变M的任何属性。现在M和L表示Ck的类型1全染色K2k+1，分别为-这样，在生成循环中的第一个顶点由和C756A. Zorzi et al. /Electronic Notes in Theoretical Computer Science 346（2019）7472k+2第一行（或列）在相应的矩阵，第二个顶点表示的第二行在矩阵等。为了证明CkK2k+1是兼容的，我们必须满足条件和CA. Zorzi et al. /Electronic Notes in Theoretical Computer Science 346（2019）747757n2n2k+12k+2k是1型4k+24k+42k+12k+2n6k+36k+62k+2n12k+1n2n1定义2.2。所以我们称之为CkCk的顶点vi∈Ck，其中i=k− 1，uj∈Ck，j=k− 1。为了证明定义2.2的（a）：注意N-（v i-1）具有顶点v p，其中p∈ {0，...，k− 1}，且C1（v p）= 2 p。现在注意N+（u j−1）有顶点u q，其中q ∈ {k，.， 2k−1}，且C2（u q）= 2（q −k），如果q> k且如果q = k，则C2（u q）= 2 k，因此具有相同颜色的顶点之间的距离为k +1，显然N −（v i−1）和N+（vj−1）是相容的。为了证明定义2.2的（b）：注意N+（v i−1）具有顶点v p，其中p∈ {k，.，2k−1}，且C2（vp）= 2（p−k），如果p>k且如果p=k，则C1（vp）= 2k。注意，N-（uj-1）有顶点u q，其中q∈ {0，.，k− 1}，且C1（u q）= 2 p + 1，如果q≤k/2− 1且C1（uq）= 2q，则为为了证明定义2.2的（c）：由于我们使用相同的拉丁方L来生成全着色，并且改变表示N−（vi）N+（vi−1）中的边的单元的颜色的唯一部分是项并且我们在L中做一些改变来改变由（i）所表示的颜色，集合N−（vi）N+（vi−1）与N−（uj）N+（uj−1）相容。 图4b示出了表示与由拉丁方L表示的着色兼容的有效全着色的矩阵M。Q引理3.3被用于定理3.4以证明我们的主要结果。引理3.3如果z ≥ a2− a，则nx，y ≥ 0，使得z = xa + y（a +1）。证据 这个证明是用z中的归纳法得到的。 如果z = a2− a，则z = xa +0（a+1），其中x =a−1。 假设对任何z1> a2−a，z1=x1a+y1（a+ 1）。 对于z2 =z1 + 1：如果x1> 0，则z2 =（x1− 1）a+（y1 + 1）（a + 1）。 如果x1= 0，则：z1 = 0 a+ y1（a + 1），当z1> a2−a时，y1≥a−1。 所以我们可以写z1=（a+1）（a−1）+（y1−（a−1））（a+1）=a2− 1+（y1−（a−1））（a+1），然后z2=x2a+y2（a+ 1），其中x2=a，y2=y1−（a−1）。Q注意引理3.3中给出的阈值是紧的，因为这是一个经典的线性丢番图方程，已知如果z=a2−a− 1，则z=xa+y（a+ 1）没有有效的整数解。定理3.4偶数k ≥ 2且n ≥ 4k2+ 2k的图Ck是1型图.证据 根据引理3.3，n=x（2k + 1）+y（2k + 2），那么我们只需要组成x乘以Ck和y乘以Ck。Q命题3.5对于固定偶数k，其中2k +1≤n≤ 4k2 + 2k， 2k2−k图n证据 证明可以通过s 中 的 归纳来进行，s表示将组成目标图的图对于s= 2：我们有图Ck，K4k+3C、k，其具有类型1着色，图CkK2k+1K2k+1K2k+2C、kK2k+2分别表示注意，2k− 2-满足2k + 3≤n≤ 4k + 1-的图Ck不完全有色人种 对于s= 3： 我们有图CkK6k +4K6k+5C、k中，这C和C得双曲余切值.和C和C得双曲余切值.得双曲余切值.758A. Zorzi et al. /Electronic Notes in Theoretical Computer Science 346（2019）7472k+1（2s）k+s+l2k+1n2k+1nnn1nn2nnnKn2k+12k+2...4k+14k+24k+34k+44k+5...n 4k²+2k3Δ+1Δ+1...Δ+1Δ+1Δ+1Δ+1Δ+1...Δ+14Δ+1Δ+1...Δ+1Δ+1Δ+1Δ+1Δ+1...Δ+15Δ+1Δ+1...OΔ+1Δ+1Δ+1O...Δ+16Δ+1Δ+1...OΔ+1Δ+1Δ+1O...Δ+17Δ+1Δ+1...OΔ+1Δ+1Δ+1O...Δ+18Δ+1Δ+1...OΔ+1Δ+1Δ+1O...Δ+19Δ+1Δ+1...OTCCOTCCO...-10Δ+1Δ+1...OΔ+1Δ+1Δ+1O...Δ+1..............................-偶数kΔ+1Δ+1...OΔ+1Δ+1Δ+1O...Δ+1奇kΔ+1Δ+1...OTCCOTCCO...-图五、这项工作的贡献突出。先前的结果可以在图1中看到。图可以通过整理图Ck得到K2k+2图中在步骤s= 2中获得。注意，2k− 3个图不是全着色的。用于给定3f（k）-可以分解成更小的相容图。定理4.1若n >f（k），则Ck可以分解为两个循环的幂图Ck和Ck，使得n=n1+n2和Ck，Ck是兼容的。n1n2n1n2证据 设G是t-全可染的且n> f（k）.由于n> f（k），则根据鸽子洞原理，至少有一对顶点wx，wy∈V（Ck）使得Ck[N[wx]]和Ck[N[wy]]具有相同的和着色（保持元素的循环顺序因此，我们可以分解k分解为两个幂次循环图Ck和Ck，其中n1+n2=n，定理3.1中应用的反向运算，其中wx表示顶点vj，表示顶点uj。Q和C和C和CCA. Zorzi et al. /Electronic Notes in Theoretical Computer Science 346（2019）747759nnnnnN. Trotignon和K. Vuskovi′c[13]定义了一个分解被称为极值，如果至少有一个块是简单的，即，它不能被分解成更小的块。如果我们递归地应用定理4.1的同样推理，我们可以生成一个极值全着色树分解，使得：树的根是圈图Ck的原幂，两个兄弟节点是相容图，这两个节点的拼贴生成父节点，并且树的每个叶节点都是相容图。树是一个简单的块-Ck图，其中nl≤f（k）. 请注意，每个节点小于原始图Ck的大小，并且分解树的节点数是n的线性函数。此外，每个叶节点的大小小于f（k）。因此，对于固定的k，我们可以设计一个基于分解的循环Ck全色a幂多项式时间算法由于每个叶具有与其兄弟节点的着色兼容的总着色。适当地使用数据结构和精确的复杂性分析，实际上会表明这种算法在n中是线性的，假设k是固定的。5结论在这项工作中，我们证明了，如果n大于一个给定的阈值，那么每一个图Ck偶数k是类型1。我们的结果实际上是更强的，因为我们证明了这种图的TCC，并给出了一个线性时间最优的算法来完全着色它们。结果渐近地证明了Campos和de Mello[4]提出的猜想，并将满足猜想的未知图减少到很小的数目.我们的结果如图5所示，图5与图1相结合，显示了我们的结果对循环图总着色能力的贡献。除了我们对偶数k的主要结果外，对于奇数k，我们也有特定k值的计算结果，即k= 5和k= 7。这些结果指出了一条通往更通用的技术的道路，该技术也可以应用于奇数k。本工作中提出的所有技术都可以扩展：我们可以通过简单地增加用于生成总着色的种子集的大小来扩展由第3节中提出的技术着色的图的集合。 定义2.2 不存在对颜色数量的任何限制，可以使用相同的思想通过给出Δ（G）+2相容的全染色证明了TCC。第4节中给出的框架可以扩展到完全着色其他类的图，主要是具有类似结构分解的图类，例如循环图。本文中提出的用于循环幂的全着色树分解与Robertson和Seymour [11]定义的树分解以及树宽的概念密切相关。因此，另一个有趣的方向将是扩展我们的技术，以提高艺术级的全着色问题的类有界树宽的图。760A. Zorzi et al. /Electronic Notes in Theoretical Computer Science 346（2019）747引用[1] S.M. J.T.阿尔梅达Belotti，M.M. Omai和J.F.H.边 循环的三次和四次幂的全染色 在第 六届 拉丁美洲图 形派 系研讨会上 发表 （2014年）。[2] M. 贝赫扎德 图及其色数 密歇根州立大学博士论文（1965年）。[3] C.N. Cam pos. OP roblemadaColo rapuzzo total emClassesdeGrafos. PhDthesis，UniveraducadeEstadual de Campinas-Unicamp（2006）.[4] C.N.坎波斯和C·P·德梅洛关于圈的幂全染色的一个结果。Discrete Applied Mathematics，155，（2007），585[5] A. G. Chetwynd和A. J. W. Hilton. 色数猜想的一些改进Congressus Numerantium，66，（1988），195[6] 厘米de Figueiredo，J. Meidanis，and C.P. de Mello. 对偶弦图的全色数和色指数Information ProcessingLetters，70（1999），147[7] M.C. Golumbic 根路图的全染色。Information Processing Letters，135，（2018），73-76.[8] S.矶部，X. Zhou和T.西关退化图的全染色。Combinatorica，27，（2007），167-182.[9] R.C.S. 我来了C.M.H. deFigueiredo和K. Vus kovi′c没有循环的具有唯一和弦的graphs的chromaticindex。Theoretical Computer