图论研究：(爪，4K1，洞孪生)-free图的最小整数着色问题

\{\fn黑体\fs22\bord1\shad0\3aHBE\4aH00\fscx67\fscy66\2cHFFFFFF\3cH808080}可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）369-377www.elsevier.com/locate/entcs一类无爪图的为了纪念德埃里克·马雷戴安格勒. 佛雷·C·H·T·胡昂威尔弗里德·劳里埃大学加拿大滑铁卢摘要给定一个图集L，如果图G不包含L中的任何图作为导出子图，则图G是L-free的。最近，Fr′e d′ericMa r ay和合著者表明，着色问题 claw，4K1，K5无e图可以在多项式时间内求解。 在本文中，我们研究了一类相关的图。一个孔长度至少为4的诱导循环。 图G的两个顶点x，y是孪生的，如果对任意与x，y不同的顶点z，xz是边当且仅当yz是边. 双洞图是从一个洞得到的图通过增加一个顶点与洞的某个顶点形成孪生。 孔双胞胎和K5e，很有趣与线图有关。在线图的刻画中，它们属于禁止子图。本文证明了一个多项式时间算法来求解无色（爪，4K1，双洞）图。关键词：图着色，线图，爪，洞孪生，C6-孪生，C5-孪生，C4-孪生，P5-孪生1结果以Fr′ed′ericMa′ ray及其合著者的文章[9]为基础，研究了（claw，4K1，hole-twin）-free图的一个图着色问题（未给出的定义将在后面给出）.图的染色是图论中最基本的问题之一，有许多理论和实际的结果。 对于某个 整数k， 我 们 可 以 定 义 图G的k -染色为映射f：V（G）→ {1，...， k}使得对任意两个相邻顶点u，v∈V（G），f（u）f（v关键问题图的着色是：什么是最小的整数k，这样的着色存在？这个数k称为图的色数χ（G 确定图的色数被称为顶点着色问题，并且通常被认为是NP-困难的[14，10]。然而，对于某些特定的图类，这个问题可以在多项式时间内解决我们称一个图G对某个图集H是H-free的，如果G不包含H的任何成员作为导出子图。文献[9]和[17]研究了H4-free图，其中H4是任意四点图的集合对于任何H4，顶点着色，https://doi.org/10.1016/j.entcs.2019.08.0331571-0661/© 2019由Elsevier B. V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。370Y. Dai et al. /Electronic Notes in Theoretical Computer Science 346（2019）369································爪4K1C4−双C5−双胞胎C6−双胞胎P5−双床Fig. 1. 本文讨论的图已知H4-free是NP完全的或在多项式时间内可解的，除了三个例外。其中一个例外是{claw，4K1}-free图类.文[9]的结果表明，对于（claw，4K1，K5\e）-free图，顶点着色是多项式时间可解的.这个类更重要，因为它包含了4个无K1的线图。给定一个图G，G的线图L（G）定义为顶点为G的边，且L（G）的两个顶点相邻，如果它们在G中对应的边是关联的.Beineke [1]利用一组九个禁止导出子图，其中两个是爪图和K5\e图，给出了线图的一个刻画.因此，当（claw，4K1，K5\e）-free图与4K1-free线图相连时，很自然地要问：当K5\e被其它9个禁止导出子图之一所取代时，图的顶点染色的事实上，我们更进一步，提出了一个更一般的类的问题，我们引入并称之为空穴孪生。一个洞是一个长度至少4.图G的两个顶点x，y是孪生的，如果xy是一条边，并且对任意一个与x，y不同的顶点z，xz是一条边当且仅当yz是一条边.一个洞孪生是从一个洞通过添加一个顶点与洞的某个顶点形成一个孪生而得到的图。图1显示了三种最小的空穴孪晶：C4孪晶、C5孪晶和C6孪晶。定义空穴孪生类的动机是观察到Beineke的九个禁止图中有三个因此，空穴孪晶通过允许任意长度的空穴来推广这个想法。现在很自然地想知道着色（爪，4K1，双洞）-免费图的复杂性本文的目的是证明以下定理。定理1.1存在一个多项式时间算法来求解无（爪，4K1，双洞）色图.在第2节中，我们讨论了证明我们的主要定理所需的背景结果。在第3节中，我们证明了定理1.1以及必要的引理和辅助结果。最后，在第4节中，我们讨论了我们工作的重要性，以及一些悬而未决的问题。2定义和背景在本节中，我们讨论证明我们的主要定理所需的背景结果本节有两个小节。在第一小节中，我们讨论无爪图。Y. Dai et al. /Electronic Notes in Theoretical Computer Science 346（2019）369371在第二节中，我们讨论团宽度。2.1无爪图设α（G）表示G的最大稳定集的顶点数.设χ（G）表示图G的色数，ω（G）表示图G的最大团的顶点数.一个k-洞是一个有k个顶点的洞我们的结果依赖于完美无爪图的已知定理，我们现在讨论这些结果。一个图是Berge，如果它不包含一个奇洞或一个奇反洞（洞的补）作为导出子图。一个图G是完美的，如果对G的每个导出子图H，我们有χ（H）=ω（H）. Parthasarathy和Ravindra [18]证明了无类Berge图是完全的。Chv′atal和Sbihi[7]证明了无爪完美图可以在多项式时间内识别。Hsu [13]证明了这些图可以在多项式时间内着色。我们注意到Chudnovsky，Robertson，Seymour和Thomas [6]证明了一个图是完美的当且仅当它是Berge，解决了Berge的一个长期猜想[2]。完美图可以在多项式时间内被识别（C hudn ovsk y，Cor nuejols，Liu，SeymourandVus kov i′c[5]），并且它们可以在多项式时间内被最优着色（Grots chel，L ov′aszandS c hrij ver[11]）. 有关完美图的更多信息，请参见Berge和C hv′atal[3]。在Chv′atal和Sbihi[7]的文章中，建立了对我们的算法至关重要的如下结果（引理2.1 [7]设G是连通无爪图，α（G）≥ 3. 如果G包含一个奇反洞，则G包含一个C5.众所周知，α（G）= 2的图G的顶点着色是多项式时间可解的.在下一节中，我们讨论图的团宽的概念。2.2图的团宽考虑以下操作来构建图形。• 创建一个顶点u，标记为整数l。• 求几个图的不交并。• 对于某对不同的标签i和j，添加带有标签的顶点之间的所有边i和具有标签j的顶点。• 对于某对不同的标签i和j，将标签i的所有顶点重新标记为标签j。关于上面的四个操作，当一个新的顶点被创建时，它必须被分配一个标签。图的candle-width[8]是使用上述四种操作构建图所需的最小标签数量。 给定顶点集 X，Y，我们写X0Y表示X中的任何顶点和Y中的任何顶点之间没有边;这种结构称为co-join。我们写X1Y表示在X和Y之间有所有的边，这种结构被称为X的连接和Y.372Y. Dai et al. /Electronic Notes in Theoretical Computer Science 346（2019）369以下三个观察是民间传说（见[4]）。观察2.1[Follow]设G是一个图，X是G的一个有界顶点集。 则G有有界团宽当且仅当G-X有界团宽。观察2.2[Follow]设G是一个图，使得G是两个图G1和G2的并。则G有界团宽当且仅当两个G i都有界团宽。观察2.3[Follow]设G是一个图，使得G是两个图G1和G2的余并。则G有界团宽当且仅当两个G i都有界团宽。Rao[19]改进了Koblera和Rotics [15]的一个结果，证明了下面的定理。定理2.2（[19]）对任意常数c，顶点c染色是多项式时间的可解的一类图的宽度最多为c。我们的主要结果将依赖于这样一个事实，即一类特殊的图（在下面的引理）有界团宽度。引理2.3设G是一个图，使得V（G）可以被k个（不相交的）团X1，…，X k.对于顶点x，设Xix是包含x的团，NF（x）是x的邻域y的集合，使得y ∈ Xj，j= ix. 假设G满足下面的条件：（i）对于每个顶点x和任何集合Xj，其中jix，x有at（ii）对于任意顶点x，NF（x）是团. 则G的团宽至多为2k。证据由（i）和（ii），如果有两个顶点x，y是相邻的，且x∈Xi，y∈Xj，i j，则我们有NF（x）−{y}=NF（y）−{x};也就是说，x和y具有相同的在V（G）−（Xi<$Xj）中的邻域因此，我们可以划分顶点分成两两不相交的集合Y1，Y2，. Y t，Z = V（G）−（Y1<$Y2<$. （1）每个Ys是至少有两个顶点的团，（2）如果两个若顶点x，y与x∈Xi，y∈Xj相邻，i/=j，则x，y属于某个团Ys，（3）G的每条边属于团Xi或团Ys.集合Xi的顶点将与两个标签li，new，li，old相关联。我们将逐一标记G的顶点。假设我们要标记一个顶点x。(i) 如果有一个顶点的标签为li，new，则对所有i重新标记为li，old。(ii) 标签x带有标签lix，new（Xix是包含x的集合）(iii) 对于集合Xiy中x的每个邻居y，用标签liy，new(iv) 在具有新标签的顶点之间添加边（构建团Ys）(v) 对于所有i，在标签li，new和标签li，old的顶点之间添加边（构建团Xi）。(vi) 重新标记标签l i的所有顶点，新的标签为li，旧的标签为所有i。重复上述步骤，直到所有顶点都被标记。我们将使用2k标签。Y. Dai et al. /Electronic Notes in Theoretical Computer Science 346（2019）369373i=1i=1这证明了引理。在下一节中，我们将在证明定理1.1之前建立一些中间结果。3样张在本节中，我们将假设G是一个连通的（爪，4K1，洞孪生）-无图，我们将重点讨论当G包含一个奇洞时会发生什么。由于G是4K1-free的，我们知道G不含k≥8的洞Ck.所以我们假设G包含C7或C5。引理3.1设G是一个连通的（claw，4K1，hole-twin）-free图.如果G包含一个C7，则G至多有21个顶点。证据设G包含一个7孔H，顶点为h1，...，h7和边h i h i+1，其中下标取模7。G−H中的一个顶点是k-顶点，如果它与H中的k个顶点相邻。设Yi表示与hi，hi+1，hi+2，hi+3相邻的4-顶点集. 设Zi表示与hi，hi+1，hi+3，hi+4相邻的4-顶点集. 很容易看出一个4-顶点的类型必须是Yi或Zi。观察3.1G没有k-顶点k∈ {0，1，2，3，5，6，7}.证据如果G有一个k-顶点，对k∈ {0， 1， 2}，则G包含一个4K1.若G有k-顶点，对k∈ {5， 6， 7}，则G包含爪.如果存在一个3-顶点，则G包含一个C7-孪生，或爪形.从上面的观察，可以得出G−H中的顶点必须是Yi或Zi。观察3.2 Y i是一个集团。证据如果Yi包含不相邻的顶点u，v，则{hi+3，hi+4，u，v}诱导爪形。观察3.3|Y i|对于任何i ≤ 1。证据假设某个Yi至少有两个顶点u，v。根据观察3.2，uv是一条边，因此{hi+3，hi+4，hi+5，hi+6，hi，u，v}诱导出一个C6-孪晶。观察3.4 Z i是一个集团。证据如果Zi包含不相邻的顶点u，v，则{hi，hi+6，u，v}诱导爪形.意见3.5|Z i|对于任何i ≤ 1。证据假设某个Zi至少有两个顶点u，v。根据观察3.4，uv是边，因此{hi+4，hi+5，hi+6，hi，u，v}诱导出C5-孪晶。根据观察，我们认为，|V（G）|为|V（H）|+107|Zi|+107|Yi| ≤21. 我们建立了引理3.1。引理3.2设G是一个连通的（claw，4K1，hole-twin）-free图.若G包含C5，则α（G）= 2，或G有有界团宽，或两者皆有.374Y. Dai et al. /Electronic Notes in Theoretical Computer Science 346（2019）3690010证据 设G包含一个5-洞H，顶点为h1，...， h5，边h i h i+1下标取模5。 我们从观察开始。观察3.6G没有k-顶点k∈ {1，3}.证据设G有1-顶点，则G含有爪。如果存在某个3-顶点，则G包含C5-孪生或爪形.接下来，我们定义以下集合，对于每个i∈ {1，...， 5}。• 设Xi是与hi−2和hi+2相邻的2-顶点的集合。• 设Yi是不与hi相邻的4-顶点的集合.• 设R是0-顶点的集合。• 设T是5个顶点的集合。设Y = Y1. 如果X = X1，则...5. 根据观察3.6，我们有V（G）=Y<$X <$R<$T。我们需要在下面提出一些意见。观察3.7我们有TR。证据如果在点t∈T和点r∈R之间有一条边，则G有一个爪，它有t，r和H中的某两个点。观察3.8我们有TX。证据若顶点t∈T与顶点x∈X之间有一条边，则G有一个爪，其中t，x和H中的某两个顶点（不是x的邻居）。观察3.9我们有TY。证据设一个顶点t∈T与某个顶点y∈Yi不相邻，其中对某个i.则集合{y，hi −1，t，hi+1，hi}诱导一个C4-孪生。观察3.10我们有RY。证据如果在一个顶点r∈R和一个顶点y∈Y之间有一条边，则G有一个爪，其中r，y和H中的某两个顶点。观察3.11 X i是一个集团。证据 设u，v∈Xi，uv/∈E. 然后{u，v，hi+1，hi+2}诱导出一个爪形。观察3.12 Y i是一个集团。证据设u，v∈Yi，uv/∈E.然后{u，v，hi，hi+1}诱导出一个爪。意见3.13|Y i|对于i = 1，2，...， 五、证据假设某个Yi包含两个顶点u，v。根据观察3.12，uv是G的一条边。现在，{hi−1，hi，hi+1，u，v}诱导出一个C4-孪晶。观察3.14 R是一个集团。证据若R不是团，则R的两个不相邻的顶点和H的两个不相邻的顶点诱导一个4K1.观察3.15Xi的顶点u不能与Xi+1中的两个顶点相邻，Y. Dai et al. /Electronic Notes in Theoretical Computer Science 346（2019）369375根据对称性，u不能与X i− 1的两个顶点相邻。证据设u∈Xi，v，k∈Xi+1，uv∈E，uk∈E.然后{u，v，hi −1，hi，hi+1，hi+2，k}诱导一个C6-孪晶。观察3.16X i的一个顶点u不能与X i +2中的两个顶点相邻;根据对称性，u不能与Xi− 2中的两个顶点相邻。证据设u∈Xi，v，k∈Xi+2，uv∈E，uk∈E.则{u，v，hi，hi+1，hi+2，k}诱发了C5双胞胎对于一个顶点x∈Xi，对于某个i，定义NF（x）为顶点y的集合，使得xy是一条边，且y∈Xj，对于某些j每个x∈X i，我们有|N F（x）|≤ 4。I. 根据观察结果3.15和3.16，观察3.17对任意i和任意顶点x∈X i，集合NF（x）是团。证据 我们将用反证来证明这个观察。 设x是xi中的一个顶点，其中i是 假设NF（x）不是团，所以存在不相邻的顶点y，z ∈NF（x）. 首先，让我们假设y ∈Xi+1。 如果z ∈ X i+2<$Xi−2，则集合{x，y，z，h i+2}诱导出一个爪。因 此，z属于Xi−1，但现在{h i+1，h i，hi−1，y，x，z，hi−2}引入了C6-t获胜。所以wekn ow{y ， z} <$ （ Xi+1<$Xi−1 ） =<$ 。因 此 ， 我 们 可 以 假 设 y∈Xi+2 和z∈Xi−2。现在，集合{x，y，z，h i+2}诱导出一个爪。我们已经建立了观察。现在我们继续引理3.2的证明。我们知道α（T）≤2，因为否则G有一个爪，其中一个顶点在H中，而另三个顶点在T中。设T包含两个不相邻的顶点t1，t2.则X必须为空，否则集合{h，x，t1，t2}诱导一个爪形，其中x是X中的一个顶点，h是X在 H（根据观察3.8，X在T中没有邻居）。现在，R必须是空的，因为否则存在边rz，其中r ∈ R且z ∈ Y<$T（因为G是连通的）;这与观察3.10和3.7相矛盾。 现在，G是观察3.9中T和H的连接。集合Y<$H不能包含一个在三个顶点上的稳定集合S，否则S和T中的一个顶点诱导出一个爪。因此α（G）= 2，我们就完成了。所以我们可以假设T是一个集团。 请注意，团的宽度为2。设G1是G的去掉H_∞Y中所有顶点后得到的子图.由于集合Y是有限的（根据观察3.13），根据观察2.1，我们只需要证明G1有界团宽度。在G1中，根据观察3.7和3.8，T（如果它不为空）和X<$R之间没有边。因此，通过观察2.3，我们只需要证明由X∈R诱导的图G2具有有界团宽。在任意点r∈R和任意点x∈X之间存在一条边，否则存在一个包含r，x和H的某两个点的4K1.G2是R和X的并.通过观察2.2，我们只需要证明G3=G2−R=X有界团宽。回想观察3.17，对于每个x∈Xi，NF（x）是团。因此，G3满足引理2.3的假设，因此它有界团宽度。引理3.2的证明已经完成。现在，我们可以证明主要定理。定理1.1的证明设G是一个无（爪，4K1，双洞）图.我们可能376Y. Dai et al. /Electronic Notes in Theoretical Computer Science 346（2019）369设G是连通的且α（G）≥3。我们可以假设G不是完美图，否则我们可以使用Hsu[13]的算法在多项式时间内对无爪完美图进行着色。 因此G包含一个奇洞或奇反洞。 根据引理2.1，我们知道G必须包含一个奇洞H。由于α（G）4，H是一个7-洞或5-洞。<如果H是一个7-洞，那么根据引理3.1，G有一个有界的顶点数，我们就完成了。H是一个5孔。根据引理3.2，G有界团宽，我们就完成了。4结论和未决问题本文证明了对于一类无（爪，4K1，双洞）图，顶点着色问题可以在多项式时间内求解。对于无爪图[12]和4K1-free图[16]，该问题是NP-困难的。对于无{claw，4K1}图类，顶点着色的复杂性是未知的.见[9]和[17]关于这个问题的背景。我们把这作为一个开放的问题来结束我们的论文。确认这项工作得到了加拿大三理事会研究支持基金的支持。 福利和CT。Ho`ang）分别得到了NSERC个人发现补助金的支持。引用[1] 低气压Beineke。导出图的特征。Journal of Combinatorial Theory9（1970）129-135.[2] C. B e rg e。 FüarbungvonGraphen，derensüamtli chebzw. 他们都是从天上掉下来的。 聪明Z. 马丁-路德-哈雷-维滕贝格数学大学自然。88. 第 88章.[3] C. Berge和V. C hva'tal（eds.）. 关于完善的语法的主题。1984年阿姆斯特丹北荷兰[4] A. Brands tüadt，J. Engelfriet，H. O. Le，V.V. 洛辛 四顶点禁止子图的宽度。理论计算34（2006）561-590。[5] M. C hudn ovsk y，G. Cor nu'ejols，X. Liu，P. 西摩K。 你知道我的意思。 识别Berge图。Combinatorica25（2005），143[6] M. Chudnovsky，N.作者：Robertson，P.托马斯强完美图定理。Annals of Mathematics164（2006），51[7] V. C hva'tal，N. Sbihi。 无w-完美图的识别。 组合论杂志。B44（1988），154[8] B. Courcelle，J.Engelfriet，G.罗森伯格处理重写超图文法。 J. Comp. Sys. Sci.46（1993）218[9] D.J. Fraser，上午哈梅尔，C.T. Ho'ang，F. 马玉芳，一种4K1-free线图的着色算法，北京大学出版社. 应用数学234（2018），76-85。[10] M.R. Garey，D.S.约翰逊，L. J.斯托克梅尔。一些简化的NP-完全图问题1974年，STOC会议记录，47-63。[11] M. 格罗茨切尔湖 L ov'asz，A. Sc hrij ver. 完美图的多项式算法。 在[3]，325-356。Y. Dai et al. /Electronic Notes in Theoretical Computer Science 346（2019）369377[12] I. 霍利尔边染色的NP完全性 SIAM J. Computing 10（1981），718-720.[13] W.- L. Hsu. 如何给无爪完美图着色。Annals of Discrete Mathematics11（1981），189[14] R.M. 卡普 组合问题中的约简。 上一篇：计算机计算（R.E. 米勒和J. W.Thatcher editors），Plenum，New York（1972），85[15] D. Koblera，U.罗蒂克固定边宽图的边控制集与染色。离散应用数学126（2003），197[16] J. Krat ochv'ıl，D. Kr'al'，Zs. Tuza，G.J. 你好。不含禁止导出子图的着色图的复杂性。WG 2001，计算机科学讲义，2204（2001），254[17] V.V. Lozin，D.S.马雷舍夫少障碍图的点染色。离散应用数学（2015），http://dx.doi.org/10.1016/j.dam.2015.02.015。[18] K.R. Parthasarathy，G.拉文德拉强完美图猜想对K1，3-free图成立Journal of Combinatorial Theory Ser. B21（1976），212[19] M.娆有界树宽和树宽图上的MSOL划分问题。理论计算。Sci. 377（2007），260