路幂图的Sigma染色问题及Snark的颜色分配研究.

n3n可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）485-496www.elsevier.com/locate/entcs路的幂的Sigma染色和一些SnarkLuis Gustavo da Soledade Gonzaga1信息学学术系FederalUniversityofTechnology-Paran'aPonta Grossa，BrazilSheila Morais de Almeida2信息学学术系FederalUniversityofTechnology-Paran'aPonta Grossa，Brazil摘要考虑一个图的顶点着色，其中每种颜色都由一个自然数表示。 的颜色和顶点是其相邻顶点的颜色之和。Sigma染色问题是关于确定图G的Sigma色数σ（G）的问题，σ（G）是图G的一个染色的最少颜色数使得任意两个相邻顶点的颜色和是不同的。本文证明了当2≤k≤n−1时，σ（Pk）≤ 3，并确定了其余情形下Pk的σ色数. 这本文还介绍了Bla nunusa第一和第二类snark、Flowersnark、Goldberg和Twisted Goldberg snark的σ色数。关键词：Sigma着色，路幂，Snark，顶点着色1介绍图G的着色是图G的顶点的颜色的分配。在本文中，颜色用自然数表示，c：V（G）→N是图G的顶点染色，c（v）表示顶点v的颜色。如果任意两个相邻顶点u且v有c（u）c（v），则c是G的一个真点染色.考虑G的一个非正常点染色。顶点v的颜色和，记为σ（v）是与v相邻的所有顶点的颜色之和。如果每两个相邻的顶点u和v，σ（u）σ（v），则染色是G的sigma染色.的1电子邮件：lgonzaga@alunos.utfpr.edu.br2电子邮件：sheilaalmeida@utfpr.edu.brhttps://doi.org/10.1016/j.entcs.2019.08.0431571-0661/© 2019作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。486 LGS Gonzaga，S.M. de Almeida /理论计算机科学电子笔记346（2019）485-496nn1nnnnn3图G的一个sigma染色的最小色数称为图G的sigma色数，记为σ（G）。Sigma染色问题是给定一个图G，确定G的Sigma色数。Sigma着色问题是由Chartrand和Zhang [1]在2008年作为研究项目引入的。在2010年，Chartrand等人发表了第一篇关于这个问题的结果的论文[2]，确定了r≥2的完全图、圈和完全r-部图的sigma色数。在同一工作中，[2]证明了对任意图G，σ（G）≤χ（G），其中χ（G）是G的一个正常点染色的最少颜色数。据我们所知，很少有其他的工程上的西格玛着色问题。Dehghan等人[3]证明了判定一个图G是否有σ（G）=s，对任意固定的s≥3，是一个NP完全问题。Dehghan等人[3]还证明了判定一个三次图G是否有σ（G）= 2是一个NP完全问题。对于循环图，Luzon等人[7]确定了Cn（1，2），Cn（1，3），C2n（1，n）的sigma色数.给定一个图G，顶点v的度deg（v）是G中与v相邻的顶点的个数，G的最大度Δ（G）是G中顶点的最大度。注意，σ（G）= 1当且仅当对G中任意一对相邻顶点u和v，deg（u）/=deg（v）。因此，任何n阶路图Pn，当n≥2且n/= 3时，σ（Pn）≥2.由于Chartrand等[2]证明了对任意图G，σ（G）≤χ（G），且当n≥2时χ（Pn）= 2是一个众所周知的结果，则当n≥2且n =3时，σ（Pn 通过检验，可以检验出σ（P3）= 1.路的幂Pk，其中n > 0且<0kn<，是具有n个顶点v0，v1，.的简单图， vn−1使得（v i，v j）∈ E（G）当且仅当，0 <|i−j| ≤ k。注意，有n个顶点的路图是图P，其西格玛色数是已知的。 此外，完全图是路径Pn-1的幂，Chartrand等人[2]证明了σ（Pn−1）=n。考虑到这些结果，本文的工作扩展了关于路的幂的sigma色数的知识。当k= 2和k >n−1时，我们确定σ（Pk）。 本文中提出的证明工作提供了用于这些最佳西格玛着色多项式时间算法图表。请注意，许多这些图都有σ（Pk）≥3，根据Dehghan等人[3]，判定图G是否有σ（G）=s，对于任何固定的s≥3，是一个NP完全问题。我们还证明了对于其余的开情形，σ（Pk）≤3由于Dehghan等人[3]证明了判定一个三次图G是否具有σ（G）= 2是一个NP-完全问题，因此考虑三次图子类的Sigma着色问题是一个有趣的问题。因此，本文也给出了Blanu的σ色数，它们分别是第一和第二族的S-型、Flower-型、Goldberg-型和TwistedGoldberg-型.对于所有这些类别的三次图的证明结果在多项式时间算法的最佳西格玛染色。因此，对于这些类的snark，Sigma着色问题的决策LGS Gonzaga，S.M. de Almeida /理论计算机科学电子笔记346（2019）485487n我2理论框架本节介绍的定义和以前的结果是必不可少的发展这项工作。v的邻域N（v）是与v相邻的所有顶点的集合。v的闭邻域N[v]是集合N（v）<${v}。 如果对于两个顶点v和u， 他们被称为强双胞胎。如果图G的每个顶点v都满足deg（v）= 3，则G是三次图。Snarks是色数为4且没有任何桥的三次图。图Pk的一个标准序是顶点的线性排序（v0，v1，. vn-1）使得顶点相邻当且仅当，0 <|i − j| ≤ k。注2.1给出了相邻顶点度数相同的图的sigma色数的下界注2.1[2]设G是一个非平凡连通图.则σ（G）= 1当且仅当G的每两个相邻顶点有不同的度.注2.2增加了以前由任何图上的强孪生数建立的下界。注2.2[2]如果u和v是图G中的两个相邻顶点，使得N[u]=N[v]，则对G的每一个sigma染色c，c（u）c（v）.注2.3是注2.2的一个直接结果，它是每个完全图的sigma色数的一个下界事实上，由于定理2.4，这个下界是紧的。注2.3[2]如果H是图G中的k阶完全子图，使得对H的任意两个顶点u和v，N[u] =N[v]，则σ（G）≥k.定理2.4给出了任意图的sigma色数的一个上界。定理2.4[2]对任意图G，σ（G）≤χ（G）.Dehghan等人 [3]定义一个图G的一个sigma划分为G的顶点集的一个划分，[P0，P1，...，P σ（G）− 1]，使得对于每个边uv都有一个指数i，其中u和v在P i中有不同数目的邻居。 设s≥Δ（G）+ 1，一个常数如果每个集合Pi，0≤i≤σ（G）−1的顶点都用色s，我们得到了图G的一个最优sigma染色[3]。注释2.5是Dehghan等人工作中提出的观测结果[3]的第11段。注2.5设G是一个非平凡连通图，用色集{x1，x2，x3，...， xn}使得对于1 ≤ i ≤n，满足xi+1> Δ（G）xi. 则G中满足deg（v）/=deg（u）的两个顶点u和v都不具有σ（v）=σ（u）。3桥是连通图G中的一条边e，使得G−e是不连通的。488 LGS Gonzaga，S.M. de Almeida /理论计算机科学电子笔记346（2019）485-496、、、3n、、、nnnnnnnKi=1ΣΣ−.Σnn2n322都是真的nn的顶点的度为Δ（P k）。2nnnΔλ（di））−λ（bi） +2j=1j=1（n（1）A=（λ（aj）。3关于路径本节中给出的结果根据k定理3.1当k≥n时定义σ（Pk）;定理3.2当n−1 3时，σ（Pk）下面的定理定义了一个图的sigma色数，当k≥n，注意当k=n− 1时，图Pk是一个Kn，定理仍然定理3.1在一个图Pk中，其中k≥，n，，σ（Pk）=nΔ，其中nΔ是证据 由于Pk中的每对顶点u和v，其中deg（v）=deg（u）= Δ（Pk）n n是强壮的双胞胎，那么他们需要用一种独特的颜色来着色，和是两两不同的2.2. 由于这个原因，有可能对Pk给出一个具有nΔ颜色的sigma着色。为了表示具有n个Δ颜色的Pk的sigma着色，考虑这个图的顶点，按照标准序排序，将被划分为三个子集A，B和D，使得A={vi：0≤i≤n−k− 2}，B={vi：k+ 1≤i n}，D包含所有度为Δ（Pk）的顶点。设ai是A中度为Δ（Pk）−i的顶点，1≤1，因为存在相邻的顶点，相同程度。首先，考虑k >3且k=n−2的情况。假设图Pk的顶点是标准序的。将Pk的顶点划分为四个集合n nX0， X1， X2和 X3，使得Pk的前k +1个顶点在X0 中， X1={vk+1}， X2={vk+2，vk+3，.，v2 k +1}和X3 ={v2 k +2，v2 k +3，.，v3 k +1}。设0 ≤ i为每个集合Xjbyxj的 第 i 个 <顶点|XJ|且0≤j≤3。考虑两种颜色a和b，使得b >Δ（Pk）a。用颜色a给集合X0和X2的每个顶点着色，用颜色b给集合X1和X3的每个顶点着色。这样，具有不同度的顶点具有不同的颜色和，由注释2.5。因此，集合X 0的第k个顶点和集合X 3的顶点与它们的邻居有不同的颜色和，注2. 5。该着色的顶点的色和为：σ（x0）=ka;σ（x0）=（k+i-1）1）a+b，对于1≤i≤k;σ（x1）=2ka;σ（x2）=（2k−2−i）a+（2+i）b，对于 0≤ik;σ（x3）=（k-i）a+（k-1）b，其中0 ≤ik<. 因此，使用所提出的着色，图的所有顶点具有不同的色和，且σ（P）= 2。当k>n-1时，使用相同的技术对路径Pk的幂着色. 它3可以移除图Pk3k +2(in规范顺序），连续地，最多k-1次，以这样的方式，颜色和在每个顶点仍然是不同的。在此之后，可以删除结果图的第一个顶点，只要kn，每个顶点的颜色和将继续与其他人不同。这样，每个图Pk，其中n> k>n−1可以是得到，σ（Pk）= 2。Q当k不足以满足定理3.2的描述时，则可以找到一个上界，如定理3.3所证明的。请注意，如果上界不紧，则至多比sigma色数大1定理3.3在图Pk中，2 ≤k≤n−1，σ（Pk）≤3。LGS Gonzaga，S.M. de Almeida /理论计算机科学电子笔记346（2019）485491n−12k+1nnnn−nn3证据 考虑一个图P k，其中2 ≤ k ≤ n− 1且n ≤ 0（mod 2 k + 1），这样它的顶点就按规范顺序排列。设Pk的顶点集被划分为块G0，G1，.， Gn，使得G n中的前2k + 1个顶点2k +1正则序属于G0，其后的2k+1个顶点属于G1，以此类推.将G i中的顶点标记为vi，0，vi，1，.，v i，2 k，0 ≤iΔ（Pk）a和c >Δ（Pk）b。 通过这种方式，可以使用n n下面的函数λ：V（G）→ {a，b，c}对Pk的顶点着色，如下：a，如果j k，0≤j≤ 2k，且i≤0（mod 3）;b，如果j=k且i≤0（mod 3）;b，如果jk，0≤j≤ 2k，且i≤1（mod 3）;c，如果j=k且i≤1（mod 3）;c，如果ji=k，0≤j≤ 2k，且i≤2（mod 3）;以及a，如果j=k且i≤2（mod 3）。根据注2.5，度不同的顶点具有不同的颜色和。因此，图的第一个和最后一个k个顶点（按规范顺序）的每个顶点与它们的邻居有不同的颜色和，因为如果度小于2k，则具有相同度的顶点不相邻。它仍然需要证明相同度的顶点有不同的颜色和。首先考虑块Gi，其中i≠1（mod 3）。在这些情况下，色和如下：σ（vi，j）=（k-j）a+（k-1+j）b+c，其中n0≤j3的任何值。如果n= 3，则P2是K3，所以σ（P2）= 3.如果n= 2，则没有简单图具有k= 2。3 3定理3.4在图Pk（k = 2，n> 3）中，有σ（Pk）= 2.n n证据 考虑图P k，k = 2，顶点在标准序中。将前六个顶点（如果存在）依次用颜色b、a、b、b、a、a着色，且b≥Δ（Pk）a。接下来的六个顶点用相同的颜色序列绘制，依此类推。我们可以通过函数λ：V（P2）→{a，b}来定义这个着色，使得λ（v6i）=b，λ（v6i+1）=a，λ（v6i+2）=b，λ（v6i+3）=b，λ（v6i+4）=a，λ（v6i+5）=a，其中i∈N。因此，σ（v0），σ（v1），σ（vn−2），σ（vn−1）具有不同的颜色和，因为它们具有不同的度数，通过Rermark 2.5。 对于其余的顶点，我们有：σ（v3j+2）= 2a +2b，σ（v3j +3）= 3a + b，σ（v3j +4）= a +3b，其中j ∈ N.注意v0和vn−1永远不相邻。如果v1和vn−2相邻，则它们的色和为σ（v1）= 3b和σ（vn−2）=a+ 2b或σ（v1）= 3b和σ（vn−2）= 2a+b。因此，σ（vi）/=σ（vi±1）和σ（vi）/=σ（vi±2）。因为k= 2，所以图具有有效的sigma着色。Q基于计算测试，在观察定理3.2和3.3的结果之后，使用蛮力算法完成。得到了所有Pk（n≤27，k≤8）的最小σ染色.随后提出了以下猜想。猜想3.5设Pk是一条路的幂，若2 1，如下所示：当j ∈ {1，6，7}时c（v i）= 1，否则c（v i）= 2. 顶点的着色当j∈ {1， 2， 3， 4， 7}且c（v1）= 2时，c（v 1）= 1否则，请执行以下操作。 将每个块g i，i着色为偶数，如下：c（v i）= 1，当j ∈{1，7，8}，c（v i）= 2，否则。当j∈ {1， 4}时，g i（i为奇数）中每个顶点的色和为σ（v i）= 6，当j ∈ {3，7}时，σ（vi）= 5;当j ∈ {2，5，6}时，σ（vi）= 4。对于顶点vi，当i = n时，σ（vi）= 4，当i = n时，σ（vi）= 5。 中每个顶点的颜色和当j∈{1，4}时，块g1为 σ（v1）= 5，当j∈ {3， 8}时，为σ（v1）= 4，σ（v1）= 3当j∈ {2，5，6}且σ（v1）= 6时， g中每个顶点的颜色和i，i，even，是当j ∈ {2，5，6}时，σ（vi）= 4，当j ∈ {4，7}时，σ（vi）= 5，当j ∈ {3，8}时，σ（vi）= 6。当j∈{1}时，若i = 2，则σ（v2）= 5，否则σ（v2）= 6.因此，由于在这个证明中描述的sigma染色上没有两个相邻的顶点具有相同的颜色和，所以σ（Gn）≤2。根据注2.1，σ（Gn）= 2.Q定理4.5当n > 3时，扭曲Goldberg T Gn有σ（G）= 2，当n >3时，σ（G）= 3，n = 3。证据 证据是直接的 ，有两种 情况。 如果n>3，则为每个块gi，其中i为奇数且i>1，如下：当j∈ {1， 4， 7}且c（vi）= 2时，c（vi）= 1否则，请执行以下操作。对每个块g i进行着色，i为偶数且i > 2，如下：当j∈{1，2，3，6，7}时c（v i）= 1，否则c（v i）= 2。剩下的是给块g1和g2中的顶点着色。 将颜色分配给g1中的顶点如下：c（v1）= 1时j∈ {1， 3， 8}，否则c（v1）= 2.对块g2着色如下：c（v2）= 1时J Jj∈ {2，3，4，6，7}，否则c（v2）= 2.当j∈ {4}时，g i（i为奇数）中每个顶点的色和为σ（v i）= 6，当j ∈ {1，3}时，σ（vi）= 5;当j ∈ {2，6}时，σ（vi）= 4;当j ∈ { 5 }时，σ（vi）= 3。当i=n时，则σ（vn）= 6和σ（vn）= 4，如果i n，则σ（vi）=σ（vi）= 5。的当j∈ {8}，σ（vi）= 5时，g i中每个顶点的色和为σ（vi）=当j ∈ {1，4，7}时，当j ∈ { 3，5 }时，σ（vi）= 4，否则，σ（vi）= 3. 颜色当j∈ {1， 3， 7， 8}，σ（v1）= 5时，块g1上每个顶点的和为σ（v1） = 6当j ∈ {5}时，σ（v1）= 4，当j ∈ {4，6}时，σ（v1）= 3. 每种颜色的颜色和当j∈ {1， 4， 7}时，g2中的顶点 σ（v2）= 5，当j∈ {2， 5， 6， 8}时，σ（ v2）= 4，并且σ（v2）= 3.因此，由于没有两个相邻的顶点具有相同的颜色和，这是一个sigma着色，并且σ（TGn）≤2。根据注2.1，当n>3时，σ（TGn）= 2当n= 3时，图TG3不存在有效的两种颜色的sigma染色. 这一事实是在对两种颜色4的所有着色组合进行计算检查后建立的。但是，可以找到三种颜色的着色。遵循前面的指示和颜色v2与3。顶点v1，v2的颜色和498 LGS Gonzaga，S.M. de Almeida /理论计算机科学电子笔记346（2019）485-49688 8 4并且V3将分别变为7、6和5，并且sigma着色将有效。因此，σ（TG3）= 3。Q4测试代码见sheilaalmeida.pro.br/codigos/ProofForTG3.txt。LGS Gonzaga，S.M. de Almeida /理论计算机科学电子笔记346（2019）485499n3nK五、结论对于路径Pk的任何幂，除了当2

下载后可阅读完整内容，剩余1页未读，立即下载