∩可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）677-684www.elsevier.com/locate/entcs围长至少为8的图是b-连续的1艾伦·伊比亚皮纳2 安娜·席尔瓦3ParGO Group - Paralelism，Graphs andOptimizationParGO Group-Paralelism，GraphsandOptimizationParGOGroup-Paralelism，Graphs andOptimizationFortaleza，CE-巴西摘要一个图的b-染色是一个真染色，使得每个色类至少有一个顶点，相邻的颜色类别。G的b-谱是整数k的集合Sb（G），使得G有k个颜色的b-染色，b（G）=maxSb（G）是G的b-色数. 图是b-连续的若Sb（G）= [x（G），b（G）] Z. 已知有无穷多个图不是b-连续的。 也是 已知围长至少为10的图是b-连续的。本文证明了围长至少为8的图是b-连续的，围长至少为7的图G的b-谱包含整数在2χ（G）和b（G）之间。 这概括了Linhares-Sales和Silva（2017）的先前结果，并告诉围长至少为7的图在某种程度上几乎是b-连续的。保留字：b-色数; b-连续;围长;二部图。1介绍设G是一个简单图（关于图论的基本术语，我们请读者参考[4]）。函数V：V（G）→N是G的真k-染色，如果|（V（G））|= k且当uv∈E（G）时，因为我们在这篇文章中只处理适当的着色，从现在开始我们把它们简单地称为着色。我们称V（G）的元素为色。 给定一个颜色i∈<$（V（G）），集合<$−1（i）称为色类I. 我们称u∈V（G）是图G中的b-顶点，如果n（N[u]）=n（V（G））.如果对于某个颜色c∈N（V（G）），颜色类c不包含b-顶点，我们可以通过将每个顶点v∈N-1（c）的颜色改变为N（V（G））\N（V[v]）中的另一种颜色来获得（k-1）-染色我们说，这种新的着色是从第一个1由 CNPq 项 目 Universal编 号 401519/2016-3 和 Produtividade 编 号 304576/2017- 4 以 及 FUNCAP/CNPq 项 目PRONEM编号304576/2017- 4提供部分支持。PNE-0112-00061.01.00/16.2电子邮件：allenr. gmail.com3电子邮件地址：anasilva@mat.ufc.brhttps://doi.org/10.1016/j.entcs.2019.08.0591571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。678A. Ibiapina，A.Silva/Electronic Notes in Theoretical Computer Science 346（2019）677一种是通过清洁颜色C。在着色中，我们不能应用这个过程，所有的颜色类至少有一个b-顶点。这样的染色称为G的b-染色。观察到最优着色不能通过所描述的算法减少颜色的数量;因此每个最优着色也是b-着色。在[8]中，作者定义了G的b-色数，记为b（G），即G有k个颜色的b-染色的最大自然k在同一篇文章中，作者证明了寻找b（G）的问题一般是NP-完全的关于b-着色的另一个有趣的方面是它对χ（G）和b（G）之间的每一个可能值的存在性。在[8]中，作者观察到立方体有2色和4色的b-着色，但没有3色的b-着色。受这个结果的启发，文[9]证明了对任意整数n≥4，完全二部图Kn，n通过从a中完美匹配具有使用2和n种颜色的b-着色，但不具有使用2和n之间的颜色数的b-着色。这就引出了G的b-谱的定义，即包含任意整数k的集合Sb（G）使得G有b-染色K颜色图G是b-连续的，如果Sb（G）= [χ（G），b（G）]<$Z.在[2]中，他们证明了对于每个有限子集S<$N−{1}，存在一个图G，使得Sb（G）=S，并且即使当给出了用χ（G）和b（G）色着色的图.现在，给定一个有k种颜色的b-染色，由于每个b-顶点至少有k−1个邻居，所以存在k个度至少为k−1的顶点（这将是k种颜色的k个b-顶点因此，如果我们定义m（G）为最大正整数k，使得G中至少存在k个度至少为m（G）−1的顶点，则有b（G）≤m（G）。这个上界是在[8]中引入的，其中作者证明了可以使用图的度列表在多项式时间内找到m（G此外，他们还证明了如果G是树，则b（G）≥m（G）−1，并且可以在多项式时间内判定b（G）=m（G）。他们的结果后来被推广到围长至少为7的图[6]（G的围长是G中圈的最小长度）。我们还提到，有许多结果表明，具有大围长的正则图具有高b-色数[3，5，13，3]。事实上，下面的猜测仍然是开放的。猜想1.1若G是围长至少为5的d-正则图，且G不是Petersen图，则b（G）= d +1。由于这些结果，研究具有大围长的图的b-连续性是有意义的事实上，在[1]中，作者证明了围长至少为6且没有长度为7的圈的正则图是b-连续的，在[11]中，他们证明了每个围长至少为10的图是b-连续的。在这里，我们将他们的结果改进到围长至少为8的图定理1.2若G是围长至少为8的图，则G是b-连续的。此外，我们还证明了围长至少为7的图是几乎b-连续的。定理1.3若G是围长至少为7的图，则[2 χ（G），b（G）]<$Z<$Sb（G）.A. Ibiapina，A.Silva/Electronic Notes in Theoretical Computer Science 346（2019）677679∈ ∈{}i∈iu给定一个图G和G的一个k色b-染色，k≥χ（G）+ 1，证明了定理1.2和1.3中的一个定理是试图用简单的证明过程得到一个k-1色的b-染色;当这是不可能的时候，我们得到这个图有一个特殊的结构，并应用非构造性的论证来获得所需的b-染色。我们提到，对于周长至少为k的图，着色问题是NP-完全的，对于任何固定的k≥3[12]。这就是为什么像定理1.2这样的结果的任何证明都被期望具有非构造性部分的原因。在下一节中，我们给出了基本的定义和结果，在第3节中，我们给出了我们的证明，在第4节中，我们对证明做了一些进一步的评论，并陈述了一些悬而未决的问题。2预赛在文献[1]中，称顶点u∈V（G）为k-虹膜，如果存在S<$N（u）使得|≥ k − 1且d（v）≥ k − 1，对每个v ∈ S（见图1）。|≥ k − 1 and d (v) ≥ k − 1 forevery v ∈ S (observe Figure 1).图1.一、在图中，我们提出了一个4虹膜。这个定义很重要，因为下面的重要引理。注意引理也意味着如果G和k满足条件，则b（G）≥k。引理2.1（[1]）设G是围长至少为6且无长圈的图7. 若G有k-虹膜且k ≥ χ（G），则G有k个颜色的b-染色.如前所述，给定G的一个k色b-染色，k > χ（G）+ 1，我们试图得到G的一个k−1色b-染色。但是，这并不总是可能的，当这种情况发生时，这是因为我们有一个k-虹膜。我们的定理是从上面的引理推导出来的。我们提到，关于没有长度为7的圈的约束只出现在上面的引理中，而不是在我们的证明中。现在我们介绍进一步需要的定义。从现在起，设G是一个简单图，且k是G的一个b-染色，其中k >χ（G）+1色。我们说u实现颜色i，如果n（u）=i，并且u是b-顶点。我们也说颜色i是由u实现的。对于xV（G）和i1，.，k，设N，i（x）是x 邻 域 中 颜 色 i 的 顶 点 的集合，即，N，i（x）=N（x）<$$>−1（i）;事实上，我们省略了上标中的<$，因为它总是从上下文中清楚可见。 这在下一个定义中也是如此。 对于子集X<$V（G），令N（X）=（x XN（x））\X.设B（n）表示n中b-顶点的集合，对于每个i ∈ {1，.， k}，设B i= B（k）−1（i）是色类i中的b-顶点的集合。680A. Ibiapina，A.Silva/Electronic Notes in Theoretical Computer Science 346（2019）677∈J给定一个集合K，使得K≠1（i），对于某个i∈ {1，...，k}，我们说颜色j∈{1，...，k}\{i}依赖于K，如果Ni（B j）<$K;用U（K）表示依赖于K的颜色集合。如果K={x}，我们简单地写U（x）。给定x∈V（G）\B（G），如果|U（x）|≥2，我们称x为有用顶点;否则，我们说x是无用的。 为 j∈ {1，.，k}，我们说x∈V（G）是j-可变的，如果x是无用的，并且存在颜色c，使得我们可以将x的颜色改变为c，而不需要创建任何b-顶点。颜色j;我们也说颜色c对于（x，j）是安全的。如果（x，j）没有安全色，我们说x是j-不变的.3证明下一个引理是我们证明中的主要成分。 与引理2.1结合，它直接导出定理1.2。引理3.1设G =（V，E）是围长至少为7的图.如果G有k个颜色的b-染色，其中k ≥ χ（G）+1，则G有k − 1个颜色的b-染色，或者G包含一个（k− 1）-虹膜。证据我们的证明类似于[11]中的证明，但我们集中在一种我们想要消除的颜色上。假设G不具有k-1个颜色的b-染色，我们证明：G有一个（k-1）-虹膜。为此，设k是一个具有k个颜色的b-着色，|然后最小化|（1）|（即，|(i.e.,它首先最小化颜色1的b-顶点的数量，然后最小化颜色1的顶点的数量）。首先，我们证明了每个x∈N−1（1）\B1都是有用的。假设不是这样，并且让x是颜色类别1中的无用顶点，即， |U（x）| ≤1。 如果U（x）=n，则 我们可以在不丢失任何b-顶点的情况下对x进行重新着色，|（1）|.如果U（x）={d}，那么我们可以通过对x进行环化和清洗d来获得k−1的b-染色，同样a矛盾因此，以下情况成立：(i) 每个x∈N−1（1）\B1都是有用的。现在，我们选择任何u∈B1并分析其邻域，以获得所需的（k−1）-虹膜。为此，以下两个要求是必不可少的。权利要求3.2令j∈ {2，...，k}。如果每个x∈N j（u）\B j是1-可变的，则以下之一成立：(ii)N（u）Bj/=;或(iii)存在一个颜色d ∈ {2，...，k}\{j}使得d依赖于Nj（u），即，N j（B d）<$N j（u）.证明：假设（ii）和（iii）都不成立，并让J通过将每个x∈Nj（u）的颜色改变为对（x，1）安全的颜色c而从得到因为（iii）不成立，我们得到U（N j（u））<${1}。因此，最多有一种颜色会丢失所有的b-顶点，即颜色1，并且由于每个x N（u）都是1-可变的，所以不会创建颜色1但由于u不是J中的b-顶点（它不与颜色j）和最小化|B1|，我们得到了B-CROSSING不能是b-着色，A. Ibiapina，A.Silva/Electronic Notes in Theoretical Computer Science 346（2019）677681i=d+1i=d+1这意味着我们可以通过清除颜色1来获得k-1颜色的b-着色。下面的主张告诉我们，（ii）或（iii）实际上总是成立的。3.3（iv）每个x∈N j（u）\B j是1-可变的，对于每个j∈ {2，.， k}。权利要求的证明：在不失一般性的情况下，假设d∈ {2，...，k}使得{d + 1，.，k}是包含某个1-可变顶点的颜色。我们计算b-顶点在u附近的颜色的数量，得到d≥k。因此，对于每个i∈ {d + 1，.，k}，设wi∈Ni（u）是1-不变顶点.通过定义，这意味着，对于每个i∈ {d + 1，...，k}，存在w i的某个邻居，如果我们改变w i的颜色，它将变成颜色为1的b-顶点;设v i是这样一个顶点。然后我们知道vi∈<$−1（1）\B1，（一）使我们|U（v i）|≥ 2。（一）以物易物，以物易物，以物易物。x∈ {v d+1，.，v k}用颜色1着色，我们得到：（1）U（vi）<$U（vl）=0，对于任意i，l∈{d+1， . ，k}， i=1。现在我想， 我们研究颜色{2，...， d}。根据权利要求3.2，在不失一般性的情况下，假设p∈ {2，...，（2）是这样的：（1）对于{2，...， p}，而（iii）对于{p +1，.， d}。为每个i∈ {p + 1，...，d}，令c i∈ {2，.，k}\{i}是取决于Ni（u）的颜色，意味着Bciget：（2）n（Ni（u））. 注意，由于G没有长度为3的圈，我们{2，.， p}{c p+1，.， c d}= 0（三）同样，因为G没有长度为4的圈，我们得到ci|{c p+1,..., c d}|= d− pcl对于每个il，即：最后，因为G没有长度小于6的圈，我们得到：K（四）{2，.，p，c p+1，.，c d}i=d+1U（v i）= 0。现在，回想一下，对于每一个i∈ {d + 1，...，k}，且对于每个i∈{p+1， . 、d}. 这意味着1∈/{cp+1， . ，cd} ≠pU（vi）. 通过比较通过等式（1）至（4），我们得到以下，这意味着如所期望的d≥kk−1≥|{2， . ，p} {cp+1， . . . ，cd}U（vd+1）.. . 单位（vk）|= d− 1 +k|U（v i）|♦≥d − 1+ 2（k − d）。现在，令N =（N（u）<$N（N（u）\{u}。 注意，因为（ii）或（iii）对每个颜色l∈ {2，.，k}，我们得到B（n）N。假设N [u]不包含（k− 1）-虹膜，否682A. Ibiapina，A.Silva/Electronic Notes in Theoretical Computer Science 346（2019）677则证明完成。这意味着{2，.，k}，比方说k，使得（ii）对于k不成立，这通过权利要求3.2暗示（iii）成立，即，在{2，...，k− 1}，比如2，使得N2（B k）<$N2（u）（观察图2）。现在，设w ∈ N1（Bk）;它存在，因为Bk中的顶点是b-顶点。 通过（i），在{2，.， k}A. Ibiapina，A.Silva/Electronic Notes in Theoretical Computer Science 346（2019）677683I=2这取决于W。但是因为B（n）<$N，我们得到一个长度至多为6的圈，这是一个矛盾。N图二、 当颜色k不满足权利要求3.2时围绕u的结构。（二）.Q现在，为了证明定理1.3，我们应用引理3.1和下一个引理。 星是指最多有一个度大于1的顶点的树，图G的直径是图G的最短路中的最大边数。在这里，正如引理2.1中所发生的那样，我们得到G中k-虹膜的存在性意味着b（G）≥k。引理3.4若图G的围长至少为7，且有一个k-虹膜，其中k≥2χ（G），则G有k个颜色的b-染色证据设u∈V（G）是k-虹膜，k≥2χ（G）.让u2，...，u k是u的邻居，使得d（u i）≥k−1，对于每个i∈ {2，.，k};设N i是u i与u不同的k−2个邻居的子集。 首先用1对u着色，对于每个i∈ {2，. k}，给出颜色i到u i和颜色{2，...，k}\{i}到N i. 用T表示集合{u，u2，...，uk}kN i，也就是说，T表示着色顶点的集合。 观察图3。不B图3.第三章。u周围顶点的子集。顶点内的标签表示其颜色。观察到着色可以很容易地完成，因为G[T]−u是由k−1颗星组成的森林此外，注意我们已经有k个不同颜色的b-顶点，因此只需要将部分着色扩展到图的其余部分。为此，设B是与{1，.， χ（G）}。 我们主张uWN1（Bk）BKNk（u）...N3（u）N2（u）1Uu2 2u 33...ukkN2N3Nk1二...K1二... K...12 ... K{w ∈ V（G）\T |n∈ N（w）s.t. n（x）∈ {1，.， x（G）684A. Ibiapina，A.Silva/Electronic Notes in Theoretical Computer Science 346（2019）677|对于每个w ∈ B ≤ 1;事实上，因为T诱导出一棵直径为4的树，如果这不是真的，那么我们将得到一个长度至多为6的圈。|≤ 1 for every w ∈ B; indeed, because Tinduces a tree of diameter 4, if this was not true, then we would get a cycle oflength at most 6.通过B的定义，我们得到每个w∈B在色类χ（G）+1，.中没有邻居，K.因此，由于k≥ 2 χ（G），我们可以用颜色χ（G）+1，.，2×（G）。最后，通过B的定义，我们知道每个w∈V（G）\（B<$T）都没有颜色1到x（G）的邻居，这意味着我们可以用这些颜色给G−T−BQ4结论证明了围长至少为8的图是b-连续的，围长至少为7的图是几乎b-连续的。这改进了文献[11]中的结果，其中他们证明了围长至少为10的图是b-连续的。在那里，作者还提出了以下问题：问题1：当G是一个周长至少为g的图时，使得G是b-连续的最小g是多少？问题2围长至少为6的二部图是b-连续的吗？回想一下，完全二部图Kn，n通过去掉完美匹配得到的图不是b-连续的，对每个n≥4[9]。因此，根据我们的结果，我们得到：5≤g≤8。我们相信，同样的技术可能会将这个界限提高到7，但不会进一步提高。特别地，我们提到引理3.1适用于围长为7的图，并且由于引理2.1，界限为8。因此，如果以下问题的答案为“是”，则我们得到g ≤ 7。问题3设G是一个围长至少为7的图，使得G有一个k-虹膜，k≥ χ（G）+1. G允许k个颜色的b-染色吗对于二部图的情形，我们认为值得一提的是关于其b-色数的一个已知猜想。回想一下b-色数b（G）的上界m（G），它是存在k个顶点且度至少为k−1的最大值k。度至少为 m（G）− 1记为D（G），如果一个图是紧图，则称它是紧图，|D（G）|int n = m（G）;这意味着对于具有m（G）种颜色的G的b-染色的b-顶点，仅存在一个候选集合。判定b（G）=m（G）是否是NP-完全的，即使对二部紧图也是如此[9].在[7]中，作者定义了一类Bm，它包含每个二部图G=（A<$B，E），使得m（G）=m，D（G）=A，G的围长至少为6.他们推测如下：猜想4.1[7]对于每个m≥3，且每个G∈ Bm，我们有：b（G）≥m（G）−1。如果G是围长至少为6的二部图，且给定G的k色b-染色，k≥χ（G）+1，则通过进一步的工作，可以从引理3.1的证明中得到：G包含一个具有以下结构的导出子图HA. Ibiapina，A.Silva/Electronic Notes in Theoretical Computer Science 346（2019）677685类似于Bk中的图的结构。尝试使用这种结构来获得具有k− 1种颜色的H的b-染色可以转化为证明猜想4.1。反过来说，我们相信证明猜想4.1的策略可以帮助着色这些图，这意味着问题2的答案是这意味着回答问题2似乎和证明猜想4.1一样难。我们还提到，在[10]中，证明了猜想4.1是著名的Erd os-F a ber-L ova′ sz猜想的一个推论，该猜想 自1972年以来一直存在，并且在很大程度上被认为是成立的。这是猜想4.1成立的有力证据最后，由于对于围长至少为6的二部图，在获得b-连续性方面已经存在困难，也许一个好的选择是看看g的下界是否为tig ht。所以，我们提出了一个棘手的问题：问题4：是否存在围长为5的图不是b-连续的？引用[1] R. Balakrishnan和T.卡瓦斯卡Kneser图的b-染色 离散应用数学，160：9[2] D. Barth，J. Cohen，and T.费克关于图的b-连续性。离散应用数学，155：1761[3] M. Blidia，F. Ma Jingray和Z.泽米尔正则图的b-染色。离散应用数学，157：1787[4] A. 邦迪和苏联。Murty. 图论出版社：Spring-Verlag Press，2008.[5] S. Cabello和M.贾科瓦茨正则图的b-色数。离散应用数学，159：1303[6] V. Campos，C.Lima和A.席尔瓦 围长至少为7的图具有较高的b-色数。European Journal of Combinatorics，48：154[7] F.哈维特角Linhares-Sales和L.桑帕约紧图的b-染色离散应用数学，160（18）：2709[8] R.W.欧文和D.F.男人之爱图的b-色数。离散应用数学，91：127[9] J. 我的天啊，Zs. Tuza和M. 好的。 关于图的b-c色数。 在WG2002-Int.Workshop on Graph-TheoreticConcepts in Comp. SC. ，2002年。[10] W.- H. Lin和G.J. 张。二部图的b-染色与Erdos-fa b er-lova ′ sz猜想离散应用数学，161（7-8）：1060[11] C. Linhares-Sales和A.席尔瓦大围长图的b-连续性。Graphs and Combinatorics，33（5）：1139[12] V.V. Lozin和M.卡明斯基无长短圈图的边和顶点的着色Contributions do Discrete Mathematics，2（1），2007.[13] A. El Sahili和H.库伊德关于正则图的b-染色 实用数学，80：211
