没有合适的资源?快使用搜索试试~ 我知道了~
α[5927可在www.sciencedirect.com在线获取理论计算机科学电子笔记346(2019)221-228www.elsevier.com/locate/entcs独立数为3和4的S. 布斯塔曼特1,2,5智利大学的工程设计智利圣地亚哥D.A. Quiroz1,5 M.Stein斯坦1,3,5Dep artamentodeIngenier'ıaMatem'aticayCentrodeModelamientoMatem'aticoUniversidad de Chile智利圣地亚哥J. Zamora萨莫拉4,6Dep artamentodeMatem'aticasUniversidad Andres Bello圣地亚哥,智利摘要Hadwiger关于浸入序的猜想(一个由Lescure和Meyniel以及Abu-Khzam和Langston独立提出的猜想)的类似物指出,每个不包含完全图Kt +1作为浸入的图G满足χ(G)≤ t。如果这个猜想成立,则意味着每个具有n个顶点且独立数为α的图都包含K[n|作为浸入(如果α= 2,则两个已知语句是等效的)。浸入猜想的解决比图的子项猜想更成功:不仅已知Kt+1-浸入自由图的色数的线性上界,而且目前已知的最佳上界非常接近于最优。也就是说,目前这方面的最佳界是由Gauthier,Le和Wollan提出的,他们最近证明了每个不包含Kt+1作为浸入的图满足χ(G)≤3。54t+ 7。他们的结果意味着任何n阶独立数为α的图包含Kn3 .第三章。54α −c|作为浸没,其中C<1. 98.此外,同一作者证明,每个图独立数为2的函数包含K2[n]作 为 浸入。我们证明了任何n个顶点且独立数为3的图至少在[2n<$−1个顶点上包含团浸入,任何n个顶点且独立数为4的图至少在[4n<$− 1个顶点上包含团浸入。因此,与上面的界限相比,在这两种情况下,我们大致加倍所获得的浸没的大小保留字:图浸入,独立数,色数,Hadwigerhttps://doi.org/10.1016/j.entcs.2019.08.0201571-0661/© 2019作者。出版社:Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。222S. Bustamante等人/理论计算机科学电子笔记346(2019)221√α(G)4不[|nα(G)1介绍对于图G,设χ(G)表示其色数. Hadwiger[13]的一个著名猜想指出,任何不包含完全图的图G,Kt+1作为子式满足χ(G)≤t。该猜想仅在1≤t≤ 5时成立;t= 4和t= 5的证明依赖于四色定理定理对于一般的t,色数的当前最佳上界来自Kostochka [16]和Kostochason[20]的(独立)结果,并且是χ(G)∈O(t log t).设α(G)表示图G的独立数,并且容易看出χ(G)≥ [n |. 因此,四色定理意味着每个n个顶点的平面图都有一个大小为[n]的独立集,|. 一九六八年Erd讨论了这个推论是否可以在不使用FourColor的情况下得到定理这个问题仍然是开放的(见[5])。类似地,Hadwiger猜想,如果是真的,则意味着不包括Kt +1作为子图的n个顶点的图G包含大小为[ n]的独立集|,这将是最好的可能,证明了不相交工会的副本K t。或者,我们可以说Hadwiger猜想暗示了每个n -顶点图都包含一个大小至少为[ n]的团子式|.如上所述,不知道除了完全图Kt+1之外的每个图G是否满足χ(G)≤2t(实际上,Hadwiger猜想的但在1982年,Duchet和Meyniel[9]证明了任意n阶图G都含有小集团n. 在这方面已经有了一些改进2α(G)−1界[3,11,14,15,22],最好的界,由于Balogh和Kostochka[2],被[cα(G)|,其中c是常数,c<为1。95.在这个扩展的摘要中,我们将集中在图的浸入关系,这在最近几年得到了广泛的关注。 浸入关系可以看作拓扑子关系的一个变体。 如果存在一个内射函数,则称一个图G包含另一个图H作为浸入φ:V(H)→V(G)使得:(i) 对于每个uv ∈ E(H),在G中存在一条路,记为P uv,其端点为φ(u)和φ(v)。(ii) 在{P uv|uv ∈ E(H)}是两两边不相交的。我们称φ(V(H))中的顶点为浸入的分支顶点。 通过分割o-路径Puv,我们意味着我们删除路径的边,并将边uv添加到G(除非它已经存在)。所以,H是G的浸入,如果它可以从1由CONICYT、PIA/A poyaCie ntrosCie nt′fiscosyTecnol′ogicosdeExcelventureconFinan-ciamiento BasalAFB170001提供支持。2由科学技术委员会博士研究金赠款21141116支助3由FONDECYT经常赠款1183080支助4由FONDECYT经常赠款1180994支助5电子邮件:{dquiroz,mstein,sbustamante}@ dim.uchile.cl6电子邮件:josezamora@unab.clS. Bustamante等人/理论计算机科学电子笔记346(2019)221223[−c|235G通过顶点删除、边删除和分裂O-路径Puv的操作(in任何命令)。小序和浸入序是不可比的。平面图的类,而不包括K5作为一个未成年人,包含所有集团作为浸入。另一方面,最大度至多为3的图的类,同时排除K4作为浸入,包含所有团作为未成年人。然而,这两种关系确实有一些重要的相似之处。Robertson和Seymour [18,19]证明了它们都是良拟序的。 此外,本发明还如果一个图G包含一个图H作为拓扑子图,则G包含H,作为辅修课程和浸入式课程可能受到这种相似性的启发,Lescure和Meyniel[17]以及Abu-Khzam和Langston [1]独立地提出了以下猜想。猜想1.1([1,17])除完全图Kt+1作为浸入之外的所有图G都满足χ(G)≤t.这个猜想最近受到了广泛的关注,并且已经比它的小阶对应物更成功地解决了。1≤t≤ 3的情况是由Hajos猜想(在猜想1.1中用“拓扑子式”代替“浸入”)对这些情况成立的事实得出的Lescure 和Meyniel[17]以及DeVos 、Kawarabayashi、Mohar和Okamura [7]独立解决了4≤t≤6例病例。Forgeneralt,D e Vos,D vor'ak,Fox,McDonald,Mohar,andS cheide[6]是第一个给出猜想1.1的线性上界的人。 他们证明,图G不包括Kt+1作为浸入满足χ(G)≤200 t. Dvor'ak和Yepre-Myan[10]将上限改进为11t + 6。 目前最好的上界已知的是由于Gauthier,Le和Wollan[12],他们证明了如果G不包括Kt+1,作为浸入,则G满足χ(G)≤ 3。54t + 7。这意味着以下情况。定理1.2(Gauthier,Le和Wollan [12])设G是n阶图,独立数为α。则G包含Kn作为浸入,3 .第三章。54α其中C<1。98是一个常数这 似 乎 很 自 然 地 问 , 这 是 否 可 以 得 到 改 善 , 而 不 一 定 提 高 - INGGauthier,乐和Wollan这方面的第一次尝试(实际上早于[12])由Vergara[21]进行。她证明了每一个n个顶点且独立数为2的图都包含K [ n]的浸入|证明了对于独立数为2的图,这个猜想等价于猜想1.1.为了支持她的猜想,Vergara证明了每个n个顶点且独立数为2的图都包含一个K[n|- 沉浸。Gauthier、Le和Wollan[12]改进了这个结果,如下所示。定理1.3(Gauthier,Le和Wollan [12])设G是n阶图,独立数为2. 则G包含K2[n]作为浸入.对于一般独立数α,我们做如下猜想,推广-224S. Bustamante等人/理论计算机科学电子笔记346(2019)221α927[|Vergara的猜想。我们的猜想是最好的可能性,因为,如前所述,不相交的并完全图的阶t不包含浸入Kt+1。猜想1.4 [4]设G是n阶图,独立数为α. 则G包含K[n|作为一种沉浸。我们的主要结果为猜想1.4提供了更多的证据。定理1.5 [4]设G是一个n阶图,其独立数至多为3. 则G在至少[2 n<$− 1个顶点上包含团浸入。定理1.6 [4]设G是一个n阶图,其独立数至多为4. 则G在至少[4 n<$− 1个顶点上包含团浸入。这两个结果都大大改善了从Theo-rem 1.2获得的浸入的大小。我们希望,我们在这里实现的技术的进一步发展可能有助于为猜想1.4提供进一步的证据,从而为猜想1.1提供进一步的证据。事实上,在回顾这个扩展的摘要时,我们设法证明了下面的结果,它对定理1.2的每个α值都有改进。定理1.7 [4]设G是一个n阶图,其独立数至多为α。 则G包含Kn作为一种沉浸。3α−2这个扩展摘要的其余部分致力于证明Theo-雷姆1.5定理1.6依赖于类似的思想,但更复杂。对于定理1.6的证明和定理1.7的证明,我们请感兴趣的读者参考[4]。2独立数为3的在本节中,我们证明定理1.5。在开始实际的证明之前,我们先简要地概述一下基本思想。2.1证明的概述我们将对图G的顶点数应用归纳法。 在归纳步骤,我们分离三个顶点,a1,a2和a3,并使用归纳假设找到G− {a1,a2,a3}中完全图的浸入H。这个浸入H可能是我们需要的大小的一个短。 在这种情况下,我们将尝试将a1,a2,a3中的一个连接到H的分支顶点,使所选择的顶点ai成为更大浸入的新分支顶点。用于连接一个i到其他分支顶点的路径将完全属于二分图在{a1,a2,a3}和V(G)− {a1,a2,a3}之间,因此,它们不会干涉从原始浸入H开始的任何路径。我们选择三个顶点中的哪一个作为新的分支顶点ai将取决于它们各自邻域的大小和它们在不同方向上的交点。S. Bustamante等人/理论计算机科学电子笔记346(2019)221225....- 是的G−{a1,a2,a3}的部分(包含分支顶点和余数的部分对这一选择的更精确的描述是由两个主要方面中的第一个给出的。下面的Lemma2.1引理2.1将负责为新的分支顶点找到连接路径然而,可能发生的情况是,三个顶点都不合适,因为没有足够的路径来建立必要的连接(也就是说,如果引理2.1的两个主要条件中的第二个不满足)。在这种情况下,我们将能够证明我们处于以下两种情况之一无论是,对于一个顶点ai,它在G− {a1,a2,a3}中的非邻域(它跨越一个图独立数至多为2)大到足以应用定理1.3并发现所需的沉浸感。或者,有两个顶点,ai和aj,使得它们的联合非邻域(跨越完整图)具有我们浸入所需的大小。在任何一种情况下,这都完成了证明。2.2定理1.5的证明现在让我们把这个概念说得更确切些。我们需要下面的引理来建立到新分支顶点的连接。(稍后,在引理的应用中,集合M将是“旧”分支顶点的集合F或图G且v∈V(G),设N<$(v):=V(G)\(N(v)<$v). 一组顶点A支配一个顶点集B,如果B中的每个顶点在A中都有邻居。引理2.1设G是一个二分图,具有二分性(M <$Q,{a1,a2,a3}),其中M和Q不相交,且集合{a1,a2,a3}支配M。 假设k = 3,N(ai)<$N(aj)<$Q\N(ak)在不同的i,j,k ∈ {1,2,3}的所有选择上。此外,假设|≤。|≤.N(a1)<$N(a2)<$$>N(a3)<$Q。然后,G包含一个中心为3且叶在M中的星的浸入。证据如引理中所述,给定G,首先观察到N<$(a3)<$(M<$Q)的每个顶点都有一个neig hb或i n{a1,a2}。 我们把N<$( a3)<$Mi划分为两个集合N1<$i和N2<$i,使得对i = 1,2,N1 <$i中的每个顶点都与a1 相邻. (This分区不需要是唯一的。)对于每个不同的i,j,k∈{1, 2, 3},令Yij:=(N(ai)<$N(aj)<$Q)\N(ak)。根据引理的假设,我们知道,|≥ max{|Y13|、|Y23|},(1)|},(1)和|≤|Y13|+的|Y23|+的版本。|+. X. 、(二)226S. Bustamante等人/理论计算机科学电子笔记346(2019)22199关于X:=Qj=1,2,3N(aj).首先,假设可以将X划分为两个集合,X1和X2,使得|≥ |Ni|对于两个i ∈ { 1,2 }。|for both i ∈ {1, 2}. 在这种情况下,我们可以配对,对于i= 1, 2,每个顶点x∈Ni<$$>,其中顶点y x∈Y i3<$X i,使得y xy x′ 如果xi=xi,J.这意味着,对于每个x∈N1N2,都有一条形式为xai yx a3的路径,并且所有这些路径都是边不相交的。拆分或删除所有这些路径,并使用在a3和M之间的边,我们得到一个以a3为中心,以M为集合的 叶子,如你所愿。因此,我们从现在开始假设不可能将X划分为集合X1和X2,使得|Y i3X i|≥ |N i|对于两个i∈ {1,2}。这意味着,模交换索引1和2,我们有|Y23X|<|N2-N|.现在,以与之前类似的方式,我们将每个顶点x∈N1<$n与一个顶点yx∈Y13,我们将每个顶点x∈N2<$$>与一个顶点yx∈Y13<$Y23<$X配对,所有的顶点yx都是不同的。这是可能的(2)。对于所有的顶点x∈N1<$n,以及对于每个chv顶点x∈N2<$n,其中ch还没有与来自Y13的顶点配对,我们将形式为xai y xa3的路径分裂为0。对于与Y13中的一个顶点配对的顶点x∈N2,我们做以下操作。将每个这样的顶点与第二个顶点vx∈Y12配对,使得所有顶点vx不相交。这可能是因为(1)。 现在,沿着小路xa2vxa1yxa3.在对所有剩余的顶点x∈N2∈ N做了这一步之后,我们得到了所需的星浸入。Q现在我们来证明定理1.5。证据[定理1.5的证明]我们用n上的归纳法证明定理1.5对所有图的陈述。这个陈述对所有n13都是平凡的。因此我们可以假设给定的图G的阶数n≥14。若G的独立数不超过2,则可利用定理1.3。因此,我们可以假设G的独立数等于3。因此,我们可以删除一个独立集I={a1,a2,a3}. 通过归纳假设,我们知道G − I包含H:= K[2(n−3)的浸入,分支顶点为M。设Q:=V(G)\(IM)。很明显,|≥ n − 3 −,2(n − 3),> 7 n − 3。| ≥ n − 3 −, 2(n− 3),> 7n − 3.(三)我们的目标是在H的浸入中添加一个新的分支顶点,或者找到一个不同的浸入正确的大小。9S. Bustamante等人/理论计算机科学电子笔记346(2019)221227对于i = 1,2,3,设置Ni:=N(ai)和N<$i:=N<$(ai)。 由于G的独立数为3,我们知道G[N<$i]的独立数至多为2,对每一个i= 1,2,3.因此,我们可以假设,|倪氏|5
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功