无爪CIS图特征与识别算法研究

可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）15-27www.elsevier.com/locate/entcs无爪CIS图的一个刻画及CIS图LilianaAlc'ona，MarisaGutierreza，MartinMilanibircbaCONICET和CMaLP，阿根廷b斯洛文尼亚滨海大学、UP IAM和UP FAMNIT Koper摘要一个图是CIS的，如果每个极大团都与每个极大稳定集相交。 目前，没有一个好的特征或识别算法的CIS图是已知的。 我们刻画了图中的每一个最大匹配饱和度至少为2的所有顶点，并使用这个结果给出了一个结构的，有效的可测试的无爪CIS图的表征。我们对多布森、胡杰杜尔、米兰和韦雷特的问题作了否定的回答。 Comm bin. 44（2015）87在积极的一面，我们表明，问题的多布森等人。在无爪图的情况关键词：CIS图，极大团，极大稳定集，极大独立集，随机内部匹配图，无爪图。1介绍许多图类可以根据图中的团或稳定集的属性来定义（参见，例如，[7，16]）。在本文中，我们继续研究CIS图，定义为每个最大团与每个最大稳定集相交的图。这里，“极大性”指的是包容下的极大性。CIS图在一系列论文中以不同的名称进行了研究[1，2，7，8，11，12，14，25，27];名称CIS（团相交稳定集）是由Andrade等人提出的。目前，没有一个好的特征或识别算法的CIS图是已知的。识别CIS图被认为是co-NP-complete[27]，证明是co-NP-complete[28]，证明是多项式[2]。CIS图的结构很难理解，这可能与CIS图类在点删除下不是闭的这一事实有关。例如，bull，即顶点集为{v1，.，v5}和边集{v1v2，v2v3，v3v4，v2v5，v3v5}，是一个CIS图，而从bull中删除顶点v5会产生4-顶点路，它不是CIS。https://doi.org/10.1016/j.entcs.2019.08.0031571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。16L. Alcón等人/理论计算机科学电子笔记346（2019）15一些部分结果是已知的CIS属性在特定的图形类。CIS图类推广了P4-free图类，也称为余图[8，10]. Sun和Hu[25]以及Boros等人[7]分别给出了平面图类和线图类中CIS 性 质 的 多 项 式 可 测 特 征 。 点 传 递 CIS 图 是 由 Dobson 等 人 刻 画 的 。[12 ][ 15 ][16][17][18][19] Furgery，Dobson等人证明了点传递CIS图具有完美图的著名性质[20]，即图的顶点数由其团数和稳定数的乘积从上有界。他们询问该属性是否适用于所有CIS图。与CIS图密切相关的一个概念是强团。图G中的团称为强团，如果它与G的每个极大稳定集都有非空交。 因此，一个图是CIS当且仅当每个极大团都是强的。 一个团是单纯的，如果它由一些顶点和它的所有邻居。不难看出，每个强团都是极大的，每个单纯团都是强的。 Hujdur ov icetal. [16]证明了C4-free图中的团是强的当且仅当它是单纯的，从而得到了CISC4-free图的多项式可测特征.强团的概念产生了文献中研究的几个其他有趣的图形性质（参见，例如，[7、16、17、23]）。我们结果我们的结果包括两个相互关联的部分。第一、 通过证明无爪CIS图的一个合成定理（定理4.5），给出了这类图的一个结构特征.这导致了无爪图类中CIS性质的多项式时间识别算法（推论4.7）。这个结果是使用图的特征导出的，其中每个最大匹配饱和度至少为2的所有顶点（定理3.3），这一结果与Sumner对随机匹配图的特征[ 24]有关其次，我们否定地回答了Dobson等人[12]提出的问题，即CIS图G的顶点数是否一定由其稳定数α（G）和团数ω（G）的乘积从上有界更准确地说，使用小稳定数的无三角形图[18]，我们构造了一个一系列CIS图显示，即使关系|V（G）|= O（α（G）ω（G））失败对于一般的CIS图（定理5.1）。在积极的一面，我们证明了Dobson等人的问题在无爪图的情况下有一个肯定的答案（定理5.4）。论文的结构。在第2节中，我们收集了必要的符号和初步结果。在第三节中，我们刻画了每个极大匹配饱和度至少为2的所有顶点的图。在第四节中，我们证明了无爪CIS图的结构特征。在第5节中，我们构造了Dobson等人的问题的一系列反例，并在无爪图的情况下研究了这个问题。在第6节中，我们通过提出一个留给我们的问题来结束本文，即ErdSchaos-Hajnal性质是否对 CIS图类成立由于篇幅有限，引理4.2和推论4.7的证明被省略了。L. Alcón等人/理论计算机科学电子笔记346（2019）15172预赛我们只考虑有限、无向和非空图除非使用多重图这个术语，否则我们所有的图都是简单的，也就是说，没有循环或多重边。 图G=（V，E）有顶点集V（G）=V和边集E（G）=E. G的顺序是|V|. 给定SV（G），G中的S记为G [S]，定义为具有点集S和边的图集合{{x，y}|{x，y} ∈E; x，y∈S}. 图G=（V，E）的补图G是顶点集V（G）= V，边集E（G）={{x，y}| x，y∈V，x/= y，且{x，y}/∈E}。我们说G是余连通的，如果它的补数是连通的。 G的一个余连通分支是由G的一个（连通）分支的顶点集导出的G的子图。一个顶点v∈V（G）的邻域是与v相邻的顶点的集合NG（v）;它的闭邻域是集合NG [v]，定义为NG [v] = NG（v）<${v}。NG（v）的基数是v的次数，记为dG（v）。图G中的泛点是度点|V（G）|-1。用δ（G）表示G中顶点的最小度.对于集合S∈V（G），设NG（S）是所有不在S中且在S中有近邻的顶点的集合.通常，我们分别用Kn，Pn和Cn表示n-顶点完全图，路图和圈图图K3也称为三角形.用Km，n表示完全二部图，其中部分二部图的尺寸为m和n。爪是完全二部图K1，3。的事实图G与图H同构，记为yG∈H。我们知道G是H-free如果G中没有导出子图同构于H。此外，给定一个图集F，我们称一个图G是F-free的，如果对所有的F∈ F，G是F-free的.给定两个顶点不交图G和H，用G+H表示它们的不交并，即顶点集V（G）<$V（H），边集E（G）<$E（H）的图对于一个非负整数k，我们用kG表示由G的k个不相交副本组成的图。图中的团是成对相邻顶点的集合;稳定集（或独立集）是成对不相邻顶点的集合。我们说，一个集团（分别为，稳定集）是最大的，如果它是包含-最大的，也就是说，如果它不包含在任何更大的集团中（分别，稳定集）。给定一个图G，它的稳定数（或独立数）用α（G）表示，定义为G中稳定集的最大尺寸;此外，它的团数用ω（G）表示，定义为G中团的最大尺寸。图G中的匹配是一组成对不相交的边。给定一个匹配M和一个顶点v，我们说M饱和v，如果M包含一个以v为端点的边。我们有时会滥用这个术语，简单地说， 一个匹配是完美的，如果它饱和了图的所有顶点。图G中的一个内点是度至少为2的点。我们说图G中的匹配M是完美内部匹配，如果它饱和了G的所有内部顶点，也就是说，如果每个不在M中的顶点的度至多为1。完美的内部匹配在一系列论文中进行了研究，参见，例如，[3对于未定义的图形术语和符号，我们参考[26]。18L. Alcón等人/理论计算机科学电子笔记346（2019）15→2.1重图的线图的性质给定一个多重图H，它的线图是具有顶点集E（H）的简单图L（H），其中两个不同的顶点e和EJ相邻当且仅当e和EJ有一个公共端点作为H中的边. 显然，如果G是重图H的线图，则存在一个不含圈的重图HJ，使得G是HJ的线图（同构于）.这样的重图HJ可以从H得到，通过将H中连接v与自身的每个环替换为连接v与新顶点的悬垂边因此，我们可以假设，不失一般性，所有考虑的线图是无环重图的线图。任何无环重图H都可以等价地用一个简单图和一个重数函数表示。实际上，对于每一条边e∈E（H），我们用w（e）表示e在H中的重数，即H中端点与e相同的边的个数。然后，H可以等价地表示为简单图H∈V顶点集V（H）和由E（H）得到的边集，即每类重边中只保留一条代表边，并将重数函数w限制在H∈ V的边上.一个赋权图是一对（H，w），其中H =（V，E）是一个图，w：EN是权重函数。1将w解释为边的重数函数， 我们看到每个加权图（H，w）对应于一个无环重图。相应地，我们设L（H，w）表示（H，w）的线图，这是由H通过用w（e）条平行边替换每条边e∈E（H2.2CIS图当k≥ 2时，k-梳是指具有2k个顶点v1，...，v k，w1，.，w k这样， C ={v1，.，v k}是一个团，v i与w i相邻，对于所有i∈ {1，.，k}，并且有没有其他边缘。 具体地，S ={w1，...，w k}是稳定集，这表明，Fk是一个具有唯一分裂划分（C，S）的分裂图，而且Fk不是一个CIS图，因为（C，S）是一个极大团和极大稳定集的不交对.一个k-反梳是图Fk，k-梳的补图称图G中的诱导k-梳Fk是稳定的，如果存在一个顶点v∈V（G）\V（Fk），它与C的每个顶点相邻而与S的每个顶点不相邻，其中（C，S）是Fk的唯一分裂划分.类似地，具有分裂划分（C，S）的图G中的诱导k-反梳Fk被称为是稳定的如果存在一个顶点v∈V（G）\V（Fk）与C的每个顶点相邻且不与S的每个顶点相邻。下面的引理描述了CIS图的一个必要（尽管一般来说不是充分的）条件引理2.1（Andrade et al. [2]）如果G是CIS，则每个k-梳都是固定的，每个k-反梳都是固定的。如果NG[x] =NG[y]，则称图G中的两个顶点x，y为真孪生.考虑G的顶点集上由规则x_y定义的等价关系1我们用N表示所有（严格）正整数的集合L. Alcón等人/理论计算机科学电子笔记346（2019）1519当且仅当x和y是真双胞胎图G的真孪生约化是将图G的一个人，一个人。一个图称为无真孪生图，如果与它的真孪生子还原相吻合。为了以后使用，我们回顾CIS图的以下有用性质（参见，例如，[2，8]）。引理2.2图G是CIS当且仅当G的每个分支的真孪生约化是CIS。接下来，我们回顾CIS线图（简单图）的特征，Boros et al.[7]。表征依赖于以下与完美内部匹配相关的概念。我们说图H中的极大匹配M是吸收的，如果每个不在M中的顶点至多看到M的一条边，或者更正式地说，如果对于每个不被M饱和的顶点v∈V（H），M中存在一条边e，使得v的每个邻居都是e的端点。 (In特别地，这意味着v在H中的次数至多为2）。注意，如果H有一条边，那么每个完美内部匹配的最大匹配都是吸收的。定理2.3（Boros et al. [7]）设H是一个无孤立点图，G = L（H）。则G是CIS当且仅当H没有同构于公牛的子图且H中的每个极大匹配是吸收的。3随机内部匹配图一个图G是随机可匹配的，如果G的每一个匹配都可以扩展到完美匹配，或者等价地，如果G的每个极大匹配都是完美的。显然，图G是随机匹配的当且仅当G的每个分支都是随机匹配的。因此，下面的定理由于萨姆纳完全特征的随机匹配图。定理3.1（Sumner [24]）连通图G是随机匹配的当且仅当G_n= K2n或G_n= Kn，n，其中n≥1.完美内部匹配的概念自然导致以下随机匹配图的推广。我们说图G是随机内部匹配的，如果G的每一个匹配都可以扩展为完美内部匹配，或者等价地，如果G的每一个极大匹配都是完美内部匹配。使用这个术语，我们注意到定理2.3的下列结果，以备后用。推论3.2设H是一个没有孤立点的无三角形图，G=L（H）。则G是CIS当且仅当H是随机内部匹配的。证据紧接着定理2.3，利用如下事实：如果H是无三角形的，则H没有同构于公牛的子图，并且H中的最大匹配是吸收的当且仅当它是完美内部匹配。Q显然，图G是随机内部匹配的当且仅当G的每个分支都是随机内部匹配的。在下一个定理中，我们20L. Alcón等人/理论计算机科学电子笔记346（2019）15J刻画连通随机内部匹配图的特征。图中的叶子图G的一个叶扩张是通过对每个顶点v∈V（G）添加一个由两两不相邻的新顶点通过边连接到v的非空集合Lv而从G定理3.3连通图G是随机内部匹配的当且仅当G是某个图的扩张，Gn=K2n，n ≥1，Gn=Kn，n.是的。若G是随机可匹配的，则G是随机内部可匹配的.现在假设G是图GJ的叶扩张。设M是G中的一个极大匹配，v∈V（G）是G的一个内顶点 则v∈V（GJ）且存在一个度为1的顶点VJ使得vvJ∈E（G）. 如果v不是M-饱和的，则vJ也不是，因此M{vvJ}是适当包含M的匹配，与M的极大性相反。因此，v在M中，由于v和M是任意的，G在内部是随机匹配。现在假设G是一个连通的随机内部匹配图。显然，G至少有两个顶点，因此δ（G）≥1。设δ（G）≥2。则G的所有顶点都是内部的，因此G是随机匹配的。通过定理3.1，G = K2n或G = Kn，n，其中n≥2. 当δ（G）=1时，则成立。 我们可以假定G至少有三个顶点，否则G∈= K2，我们就成立了.特别地，对于G的每个叶，它的唯一邻居是一个内部顶点。设L表示G中所有叶子的集合，S = NG（L）表示G中叶子的所有邻居的集合，R=V（G）\（L<$S）.若R=0 ，则 G 是 G[S] 的 叶 扩 张 ， 且 we 是 完 成 的 .所 以 我 们 可 以 假 设 R1=1 。Foreverys∈S，fixavertexsJ∈L与s相邻，令MS={ssJ|s∈S}。 设MR是极大匹配图G[R]。则MR<$MS是G中的极大匹配.由于G的内部顶点集恰好是S<$R，并且G是随机内部匹配的，MR<$MS饱和S<$R中的所有顶点。因此，MR饱和R中的所有顶点。由于MR是G[R]的任意极大匹配，我们推断G[R]是随机匹配特别地，G[R]的每个连通分支都有偶数阶。（定理3.1精确地刻画了G[R]的结构，但在其余的证明中我们不 因为G是连通的，所以它有一个边形式为rv，其中r ∈ R且v/∈ R。由于R中没有顶点在L中有邻居，我们有v∈S。则集合MJ=（MS\{vvJ}）<${rv}是G中的匹配.将M扩张为G中的一个极大匹配M。由于G是随机内部匹配的，M饱和SR中的所有顶点。设C是G[R]的包含r的分支，MC是M的完全包含在C中的边集.通过构造，M中的每一条饱和C\{r}中一个顶点的边都属于MC.然而，这意味着C是奇数阶的，这与G[R]的每个分量都是偶数阶的事实相矛盾。 这就完成了证明。QL. Alcón等人/理论计算机科学电子笔记346（2019）15214无爪CIS图在本节中，我们开发了无爪CIS图的结构特征。我们从几个引理开始，给出了无爪图是CIS图的必要条件。gem是从4顶点路径P4通过添加一个通用顶点而获得的图。引理4.1设G是无爪CIS图。G是自由的。证据设G是一个无爪CIS图，其中包含一个gem的导出拷贝，比如在顶点集{s，t，u，v，w}上，其中（s，t，u，v）是一条路，w与{s，t，u，v}中的所有顶点相邻。 由于G的子图由{s，t，u，v}同构于诱导2-梳且G是CIS，引理2.1暗示存在一个顶点x∈V（G）\{s，t，u，v}使得{tx，ux} ∈E（G）且{sx，vx}E（G） =. 很明显xw。对于一般情况，xw/∈E（G），否则{w，s，v，x}在G中诱导出一个爪形。 这意味着{s，t，u，v，w，x}诱导在G.（实际上，G的补包含一个具有团{s，v，x}和稳定集{t，u，w}的梳F3。）根据引理2.1，G包含一个顶点y∈V（G）\{s，t，u，v，w，x}，它与团{t，u，w}中的每个顶点相邻，与稳定集{s，v，x}中的每个顶点不相邻. 但是现在，顶点集{s，t，x，y}在G中诱导出一个爪，这是一个矛盾。Q我们用W4表示4-轮，即从4-顶点圈C4通过添加一个泛顶点而得到的图。引理4.2每个连通和共连通的无{claw，gem}图都是无W4图.Kloks等人在[19]中证明了无{claw，gem，W4}图类恰是多米诺骨牌类，即每个顶点最多包含在两个极大团中的图此外，多米诺骨牌恰好是无三角形多重图的线图;参见[22]。这个结果与引理4.1和4.2一起意味着以下内容。推论4.3每个连通和共连通的无爪CIS图都是连通的无三角重图的线图。一个类似于引理2.2的引理对无爪图成立。引理直接从定义中得出。引理4.4图G是无爪的当且仅当G的每个分支的真孪生约化是无爪的。引理2.2和4.4意味着在研究CIS无爪图时，我们可以将注意力限制在连通的真孪生无爪图上。因此，下面的定理给出了无爪CIS图的完整结构刻画给定一个图G，G的冠（具有K1）是由G通过添加对每一个顶点v∈V（G），定义一个新的顶点VJ，并使VJ与v相邻.请注意，G的冠是它的一个特殊的叶延伸22L. Alcón等人/理论计算机科学电子笔记346（2019）15定理4.5设G是连通的真孪生无爪图。则G是CIS当且仅当以下之一成立：(i) 对p≥0和q∈{0，1}，G ∈ = pK 2 + qK 1.(ii) G_n= L（Kn，n），其中n≥1.(iii) G_j= L（G_J<$K_（1）），对于某个三角形自由顶点G_J.证据设G是连通的无真孪生CIS无爪图。首先假设G不是共连通的，设G1，.，Gk（其中k≥ 2）是余分量ofG.由于k≥2且G是无爪的，所以每个余分支Gi的稳定数至多为2.因为根据引理4.1，G是无gem的，所以每个余分量Gi是无P4由于每个至少有两个顶点的P4[10]），每个Gi要么是K1要么是不连通的。由于α（Gi）≤2，我们推断每个Gi要么是K1，要么是两个完全图的不交并.此外，由于G是真孪生自由的，所以至多有一个Gi是单顶点图，并且每个α（Gi）= 2的Gi同构于2K1.因此，G=pK2+ qK1，其中p ≥ 0，q ∈ {0，1}.假设G是连通的。由推论4.3可知，存在一个无三角形的重图H，使得G=L（H）。显然，我们可以假设H没有孤立的顶点。由于G是无真孪生的，所以H是一个简单图。 根据推论3.2，H是随机地在内部可匹配的。 定理3.3表明，对于某些情况，n≥1，或H是某个（无三角形）图HJ的叶扩张.在前一种情况下，G∈=L（Kn，n），其中n≥1。在后一种情况下，G是真的-twin-free的事实意味着H是H J 的 电 晕，th a tis，G=L（H J<$K1）。在逆方向上，设G_n=pK2+qK1，其中p≥0且dq∈ {0， 1}。由于CIS图类在补下是闭的，因而证明了图pK2+qK1是CIS图.这很容易从定义中引理2.2 其次，证明了对于任意的无三角形图Gj，G∈=L（Kn，n）或对于任意的无三角形图Gj，G ∈ = L（Gj <$K1），当m∈n≥1时，G∈=L（KN，N）. 在这种情况下，定理3.3意味着G_n=L（H），其中H是一个没有孤立的随机内部匹配的无三角形图顶点。 因此，根据推论3.2，G是CIS。Q定理4.5具有以下结构和算法结果。推论4.6一个图G是无爪的和CIS的当且仅当G的每个分支的真孪生2+qK1的形式，其中p≥ 0且q∈ { 0， 1}，L（Kn，n），其中n≥ 1;或L（Gj<$K1），其中Gj是无三角形图.证据紧接着引理2.2和4.4，定理4.5，以及所有形式为pK2+qK1，L（Kn，n）或L（GJ<$K1）的图都是无爪图的事实。Q推论4.7存在识别无爪CIS图的多项式时间算法。L. Alcón等人/理论计算机科学电子笔记346（2019）1523−∈KKKKK5CIS图阶的稳定性与团数乘积的界5.1讨论了多布森等的一个问题al我们对多布森等人[12]提出的下列问题的回答是否定的。问题1：每个CIS图G是否满足|V（G）|≤ α（G）·ω（G）？事实上，正如我们在下一个定理中所展示的，CIS图的阶甚至不能由乘积α（G）ω（G）的任何线性函数从上界定理5.1对任意正整数k，存在一个CIS图Gk，使得|>k · α（Gk）· ω（Gk）.|>k·α (G k)·ω (G k).证据 Kim在[18]中 证 明 了存在一个正整数n0， 使得对于当n≥n0时，存在n-v 顶点无三角形图Hn，使得α（Hn）≤9n logn.我们可以假设Hn没有孤立的顶点，否则我们可以只要有必要，就为每个孤立的顶点v加上一条连接v和其他顶点的边。请注意，以这种方式修改Hn不会创建任何三角形，不会更改顶点数，也不会增加稳定性数。对于整数k中的一个点，如果nk≥n0，则nk是整数中的最小点且nk≥54kn klog n k. 设G k是由H n k得到的图 通过以下两步程序：(i) 首先，通过沿H n k的每一条边胶合一个三角形来构造一个gHkJ。形式上，V（HJ）=V（Hn）<${ve：e∈E（Hn）}和E（HJ）=E（Hn）<${uve：u是e在Hnk}中的端点。(ii) 其次，设p=6knk，对于图Hkj中的eachvertexv∈V（Hnk），用pKP（Kp的p个副本的不交并）代替v. 2.将得到的图称为G k。由于Hnk是无三角形的且没有孤立顶点，所以它的最大团是边缘。因此，HKJ的最大团是由feHnk的边e的两个端点连同相关联的新顶点v有这样的优势。特别地，HkJ的每个极大团是单纯的，因此gHkJ是CIS。显然，pKp是一个CIS图。 由于CIS图类是闭于代入文[2]，我们推论出图Gk也是CIS.它的团数和稳定数可以估计如下：• ω（Gk）=2p+1 ≤3p.Gk中的一个大小为2p+ 1的团可以通过选择Hnk的任意边e，取两个大小为p的团，从pKp的每个副本中取一个替换Gk中的e的端点，以及顶点ve来获得。不难看出，在Gk中没有更大的集团。2给定两个图G和H以及一个顶点xV（G），则用H替换G中的x的运算得到在图G x和H的不交并中，通过添加NG（v）和V（H）之间的所有可能的边而获得的图中。24L. Alcón等人/理论计算机科学电子笔记346（2019）15KKΣΣJΣKKKH_n= K2n，theN2w（E（H））=x∈V（H）<$w（E（x））≤2n·Δw（H）. 若H_n=K_n，n，则h_an-顶点图HJ的一个叶扩张，则w（E（H））≤x∈V（H′）w（E（x））≤• α（G k）<9 p<$n klog n k+ n2.通过将图Hv代入图F的每个顶点v而从图F获得的图的稳定数等于图F中的稳定集的最大总重量，其中每个顶点v∈V（F）具有等于Hv的稳定数的重量（参见，例如，[21]）。因此，Gk的稳定数等于g∈HkJ中稳定集的最大总权重其中每个顶点v∈V（Hnk）的权为p，其它顶点的权为单位. 设S是一个相应的极大-弱稳定集。WritingS=Sp<$S1，其中Sp=SV（Hnk）和S1=S\V（Hnk），我们看到Sp的总重量至多为p·α（Hnk），而S1的总重量至多为|V（HkJ）\V（Hnk）|为|E（Hnk）|.α（GK）≤p·α（HN）+|E（H n）|<9个pn klog n k+ n2，如所声称的。因此，我们有k·α（Gk）·ω（Gk） α（G）·ω（G），但每个较小的无爪CIS graph GJsatisfies |V（GJ）|≤α（GJ）·ω（GJ）。首先证明G是连通的。 设G不相交，两个图G1和G2 那么G1和G2都是较小的无爪图，因此|V（G i）|≤α（Gi）·ω（Gi）对i∈ {1，2}由G的极小性成立.我们有ω（G）= max{ω（G1），ω（G2）}.不失一般性，我们可以假定ω（G）=ω（G1）≥ω（G2）.因此，|V（G）|为|V（G1）|+的|V（G2）|≤α（ G1）·ω（ G1）+ α（ G2）·ω（ G2）≤（α（ G1）+ α（ G2））·ω（ G1）= α（G）·ω（G）. 因此，G不是反例。 这个矛盾表明G是连通的。其次，我们证明了G是共连通的。如果不是，则G是两个较小图H1和H2的不交并。因为G是CIS，所以H1和H2都是CIS.因此，H1和H2是阶数小于G的CIS无爪图，这意味着|V（H i）|对于i ∈ { 1，2 }，≤α（Hi）·ω（Hi）.与上述类似的论点表明，|V（G）|为|V（H1）|+的|V（H2）|≤α（G）·ω（G）= α（G）·ω（G），一个矛盾。因此，G是连通的。现在，由于G是一个连通和共连通的无爪CIS图，推论4.3意味着G是一个连通的无三角形的多重图的线图。根据引理5.3，|V（G）| ≤α（G）·ω（G），这意味着G不是一个coun-terexample. 这个矛盾完成了证明。Q6一个开放的问题问题1的答案是否定的。下面的放松它仍然是开放的。26L. Alcón等人/理论计算机科学电子笔记346（2019）15问题2：是否存在一个整数k使得每个CIS图G满足|V（G）|≤（α（G）·ω（G））k？一个图类G称为满足E rdεos-Hajnalp ro pε，如果存在某个ε > 0，使得max {α（G），ω（G）} ≥|V（G）|ε对所有图G∈ G成立。众所周知的Erd-Hal猜想[13]提出了一个问题：是否对任意图F，F-free图类都具有Erd-Hal性质。这一猜想仍然成立（见[9]的调查）。不难看出，使用这个术语，问题2可以等效地表述如下。问题3CIS文法类是否具有E rdos-Hajnalp ro p？然而，请注意，问题3有可能只与埃尔德-霍纳猜想有表面上的联系。这是因为每个图都是CIS图的导出子图（参见，例如，[2]）;此外，对图F，F-free图类是CIS图类的子类当且仅当F是P4的导出子图。原则上，ErdEscheros-Hajnal猜想是正确的，而问题3有否定的答案，反之亦然。确认这篇文章是为了进行有益的讨论，并在这项工作的早期版本中提出建议。 第三作者的工作得到了部分支持斯洛文尼亚研究机构（I 0 -0035，研究计划P1-0285和研究项目N1-0032，J1-7051，J1-9110）。本文件的部分工作是在阿根廷和斯洛文尼亚之间的双边项目框架内完成的，部分资金由斯洛文尼亚研究机构提供（BI-AR/15引用[1] Andrade，D.五、E. Boros和V. Gurvich，非互补连通和非CIS d-图形成弱单调族，离散数学。310（2010），pp.1089-1096年。[2] Andrade，D.五、E. Boros和V.Gurvich，在图的最大团和稳定集相交，在：B. Goldengorin，编辑，图论中的优化问题：向Gregory Z致敬。古廷的60岁生日，施普林格国际出版社，占，2018页。3-[3] Bartha，M. 和E. Go mba's，Astructur etheoremformaximum internalmatchingsingraphs，InformationProcessing Letters 40（1991），pp. 289-294。[4] Bartha，M. 和M. Kr 'esz，Tuttety petheoremforgraphshavinga perf ect internal matching，InformationProcessing Letters 91（2004），pp. 277-284。[5] Bartha，M. 和M. K r′esz，D eciding thedeterministicprop p p forsolitong raph s，ArsMathematicaContemporanea 2（2009），pp. 121-136[6] Boros，E.，N. Chiarelli和M. Milan iZeroic，Equista rablebi partitegraphs，DiscreteMath. 339（2016），pp. 1960-1969年。[7] Boros，E.， 诉 Gurvi chandM. MilaniBecaic，Onequistable，split，CIS，andreelatedclassesofgraphs，DiscreteAppl. Math.216（2017），pp.47比66[8] Boros，E.， 诉 Gurvi ch和M. Milan iZarc，OnCISci rculants，DiscreteMath. 318（2014），pp. 78比95[9] C hudon ovsk y，M.， E rd？os-Hajnalconj ectu re-asurvey，J. GraphTh e ory75（2014），pp. 178比190L. Alcón等人/理论计算机科学电子笔记346（2019）1527[10]Corneil，D.G.，H. Lerchs和L.S. Burlingham，补可约图，离散应用。数学3（1981），pp. 163-174。[11] 邓，X. G. Li和W. Zang，Chv′atal关于图的极大 稳定集和极大团的猜想 ，J. 组合理论Ser.B91（2004），pp.301-325[12] Dobson，E.，A. 我的天啊，M。 Milan ipalac和G. 陈晓，陈晓，等.中国汽车工业协会.中国汽车工业出版社.44（2015），pp. 87比98[13] Erdos，P.和A. Hajnal，Ramsey型定理，离散应用数学25（1989），pp. 37[14] Gurvich，V.， 完全边色图和超图的分解。 Revisited，Discrete Appl. Math. 157（2009），pp. 3069-3085[15] Hujdur ov i'c，A.， Strong cliquesinvertex-t ransitivegraphs（2018），arXiv：1808.09534[math.CO]。[16] Hujdur ov i'c，A.， M. Milaniiiiiuc和B. Ries，Det e ctingst rongcliques（2018），arXiv：1808.08817[math.CO].[17] Hujdur ov i'c，A.， M. Milan ic和B. 格点可分割成强集团，离散数学.341（2018），pp. 公元1392-1405年。[18] 金，J.H、Ramsey数R（3，t）的数量级为t2/logt，随机结构算法7（1995），pp. 173-207[19] Kloks，T.，D. Krats ch和H. Müller，Domin oes，in：Graph-the oreticceptsincomputerscien ce（Herrsching，1994），Lecture Notes in Computer. Sci. 903，Springer，Berlin，1995 pp.106-120[20] 洛瓦兹湖完美图的一个特征，J.组合理论系列B13（1972），pp.95比98[21] 洛津河谷 诉 和M. Milan，J.C.，Apolynomial algorithmtofindaninde pendentsetofmaximum weightin afork-free graph，J. Discrete Algorithms6（2008），pp.595-604.[22] Metelsky，Y.和R.张文，张文龙，等.离散数学16（2003），pp. 438-448[23] Milan iBagarc，M. 和N. Trotignon，等稳定图的等稳定图及其计算实例，J.Graph Theory84（2017），pp.536-551[24] Sumner，D.P.，随机匹配图，J.第3卷（1979年），页。183比186[25] Sun，J.Z.- Q. 胡，平面图中极大稳定集和极大团的丁氏猜想的证明Appl. Sin. Engl. 序列26（2010），pp.473-480[26] West，D.B、 1996年，新泽西州上鞍[27] Zang，W.，Grillet定理关于图中最大稳定集和最大团的推广259-268.[28]兹韦罗维奇岛和I.Zverovich，二部双超图：一个调查和新的结果，离散数学。306（2006），pp. 801-811