≤一条路。给定一个正整数k，D的路径划分P的k-范数定义为：P∈Pmin{|Pi|，k}。可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）735-746www.elsevier.com/locate/entcs关于弧刺有向图的Linial卢卡斯河吉村1计算机系巴西圣保罗卡洛斯大学（UFSCar）Maycon Sambinelli2圣保罗大学数学与统计研究所圣保罗，布拉迪斯拉发假丝酵母属da Silva3计算机系巴西圣保罗卡洛斯大学（UFSCar）奥兰多李4坎皮纳斯大学计算机学院（UNICAMP）巴西坎皮纳斯摘要有向图D的路部分P是有向路的集合，使得每个顶点都精确地延伸到最小k -范数的路划分称为k-最优的，其k-范数记为πk（D）.有向图D的稳定集是V（D）的两两不相邻顶点的子集。给定一个正整数k，我们用αk（D）表示D中可分解为D中k个不相交稳定集的最大顶点集。1981年，Linial证明了对每一个有向图，πk（D）αk（D）都成立. 我们说有向图D是弧刺图，如果V（D）可以划分为两个集合X和Y，其中X是可迹的，并且Y至多包含A（D）中的一条弧。本文证明了Linial猜想对弧-刺有向图的有效性关键词：有向图，路划分，部分k-染色，Linial猜想.https://doi.org/10.1016/j.entcs.2019.08.0641571-0661/© 2019由Elsevier B. V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。736L.R. Yoshimura等人/理论计算机科学电子笔记346（2019）735Σn∈C1引言对于有向图D，设V（D）表示它的顶点集，设A（D）表示它的弧集。 给定一条弧a=（u，v）∈A（D），我们说u和v相邻。 集合 D中顶点u的邻居的集合，记为N（u），是所有与u相邻但与u不同的顶点的集合。在本文中，我们只考虑没有回路和平行弧的有向图。路径P是不同顶点（v1，v2，.，v l），使得对于每个i = 1，2，.，l− 1，（v i，v i+1）∈A（D）. 我们定义路径P的阶，表示为|P|，作为其顶点的数量。Hamilton路是包含V（D）中每个顶点的路。我们说一个有向图D是可迹的，如果它包含一条Hamilton路。一个圈C是一个顶点序列（v0，v1，...，v l）使得（v i，v i+1）∈A（D），对每i = 0，1，2，.，l− 1，所有的顶点都是不同的，除了恰好v0和v l重合。我们说有向图D是无圈的，如果它不含圈。一个有向图D是传递的，如果只要（u，v）∈A（D）且（v，w）∈A（D），则（u，w）也∈A（D）.给定路径P =（v1，v2，.，v l），我们用ter（P）表示P的终端顶点v l。子路径（v1，v2，...，v i）由Pv i表示，子路径（v i，v i+1，.，v i）由v i P表示，并且子路径（v i，v i+1，.，v j）表示为v i Pv j。我们用λ（D）表示D中最长路的阶。给定另一条路径Q =（w1，w2， . . . ，wf），其中v1=w1，we表示P和Q的级联，其中P=（v1，v2， . ，v1=w1，w2， . ，wf）。有向图D的路划分P是有向路的集合，使得每个顶点恰好属于一条路，我们用|P|分区中的路径数。我们说D中的路径划分P是最优的，如果不存在路径划分P J，使得|P J|<|P|.我们用π（D）表示最优路划分的基数。 给定一个正整数k，D的一个路划分P的k-范数定义为P∈P min {|P i|，k}。D的具有最小k-范数的路划分称为k-最优的，其k-范数记为π k（D）。注意π（D）=π1（D）。D中的稳定集S是V（D）的顶点的子集，使得S的每两个顶点不相邻。具有最大基数的稳定集称为最大稳定集，其基数用α（D）表示。设k是正整数，D是有向图.D的k-部分染色Ck是k个不相交稳定集的集合。每个这样的稳定集被称为一个颜色类。请注意，某些顶点可能不属于k个颜色类别中的任何一个。k-偏着色的权定义为：CK|C|它表示为||Ck||. 我们称Ck是D的最优k-部分染色如果它是一个最大权的部分着色，我们将其权表示为：αk（D）。 注意，α（D）=α1（D）。Dilworth[1]是第一个将有向图中的路划分与稳定集联系起来的人1支持通过FAPESP（grant2017/21345-7）和CNPq（grant PIBIC-UFSCar）。电邮地址：lucas. dcomp.sor.ufscar.br2由FAPESP（授权2017/23623-4）和CNPq（授权141216/2016-6）支持电邮地址：sambinelli@ime.usp.br3支持通过FAPESP（grant2017/21345-7）和CNPq（grant PIBIC-UFSCar）。电邮地址：candida@ufscar.br4由FAPESP（授权2015/11937-9）和CNPq（授权311373/2015-1和425340/2016-3）提供支持电邮地址：lee@ic.unicamp.brL.R. Yoshimura等人/理论计算机科学电子笔记346（2019）7357371950年，他证明了当有向图D是传递的和非循环的时，π（D）=α（D）。1960年，Gallai和Milgram[2]通过将等式放宽为不等式π（D）≤ α（D），将Dilworth定理推广注意等式并不总是成立的;例如，如果D是一个5阶循环，那么π（D）= 1但α（D）= 2。1976年，Greene和Kleitman[3]通过建立π k（D）和α k（D）之间的关系，找到了推广Dilworth定理的不同方法改变路径划分的最小值的概念，并允许使用多达k个不相交的稳定集来覆盖可能的最大数量的顶点。证明了对任意可迁无圈有向图D和任意正整数k，有πk（D）=αk（D）.正如Gallai-Milgram然而，这是一个悬而未决的问题，这种普遍化是否成立。这个问题是由Linial[6]在1981年提出的，被称为Linial猜想。这个猜想的某些特殊情况已经得到了证明。重点介绍了k= 1（Gallai-Milgram关于Linial猜想的最新发展的更多细节最 近 有 一 个 关 于 Linial 猜 想 的 部 分 结 果 与 这 项 工 作 特 别 相 关 。 2017 年 ，Sambinelli，Nunes da Silva和Lee证明了Linial一个有向图D是一个棘有向图，如果存在V（D）的一个划分{X，Y}使得D[X]是可迹的，并且Y是D中的一个稳定集.脊有 向 图 是 分 裂 有 向 图 的 超 类 。 很 久 以 前 ， 在 1994 年 ， Hartman ， Saleh 和Hershkowitz[4] 证 明 了 Linial 的 一 个 不 同 （ 尽 管 相 关 ） 猜 想 ， 我 们 称 之 为LinialSambinelli、Nunes da Silva和Lee[9]的证明在结构上与Hartman、Saleh和Hershkowitz的证明有一些相似之处;但是必须开发一些特殊的技术来解决Linial猜想。这项新技术的最近发现推动了这项工作。在这里，我们提出了一个扩展的使用该技术的超类的脊椎有向图。这项工作的目的是开始调查更多的超类的新技术可能适用于解决Linial猜想。我们从弧-棘有向图类开始，在下一节中定义2弧脊有向图我们说有向图D是弧-刺有向图，如果在V（D）中存在一个划分{X，Y}，其中D[X]是可迹的，且D[Y]至多包含一条弧。如果X是极大的，则弧刺有向图的一个这样的划分{X，Y}是极大的。我们使用D[X，Y]来表示D有一个这样的划分{X，Y}并且它是最大的。我们用a表示D[Y]中可能存在的唯一弧，用u和v分别表示a的 设P =（x1，x2，...， xl）是D [X]的Hamilton路。738L.R. Yoshimura等人/理论计算机科学电子笔记346（2019）735Sambinelli，Nunes da Silva和Lee [ 9 ]提出的关于脊柱有向图的Linial猜想的证明然后，确定了一个最佳部分k-染色的权重高于标准部分k-染色的有向脊图子类。这些被称为k-loose脊柱有向图。对于其余的有向图，称为k-紧脊柱有向图，它表明，典型的路径划分不是k-最优的。本文给出的弧-刺有向图的Linial猜想的证明我们假设正整数k至少为2，这在我们的证明的许多步骤中是基本的。然而，由于Gallai-Milgram设D[X，Y]是一个弧-刺有向图。我们定义D [X，Y]关于D [ X ]的某条Hamilton路P的一个典型（路）划分为{P，（u，v）}<${（y）：y∈Y− {u，v}}。显然，该路径划分具有等于min {|X|，k}+ |Y|.因此，π k（D）≤ min {|X|，k}+ |Y|.我们说P在D中是无弧的，如果D中不存在以下类型的弧：（i）（y，x1）或（ii）（xl，y），其中y∈Y;（iii）（v，x2）或（iv）（xl−1，u）;（v）（xi−1，u）和（v，xi+1）同时或（vi）（xi，u）和（v，xi+1）同时或（vii）（xi，y）和（y，xi+1）同时，其中1 q。 通过归纳假设，我们有（xt，y）∈A（D），其中q≤t≤i−1。若（y，xi）∈A（D），则P在D中不是无边界的，从而（xi，y）∈A（D）.特别地，当i=r时，我们证明了（xi，y）∈A（D），其中q≤i≤r.一个对称推理可以用来证明情况（ii）。QL.R. Yoshimura等人/理论计算机科学电子笔记346（2019）7357390推论2.3设D [X，Y]是弧-刺有向图，P =（x1，x2，…， xl）是D [ X ]的一条无边界Hamilton路。 则不存在与P的所有顶点相邻的顶点y ∈ Y。证明相反地，假设存在某个顶点y∈Y与P的每个顶点相邻。由于P是无边界的，所以（x1，y）∈A（D）.然后，通过引理2.2，（xl，y）∈A（D）;与P是无边界的事实相矛盾QLinial因此，根据推论2.3，有某个顶点xv∈X不与顶点v相邻。现在设S是X−x v的任何包含min {|X|-1，k-2}个顶点。因此，我们可以定义关于S的典型k-部分染色为{Y−v，{v，x v}}<${{x}：x∈S}}。显然，这种k-偏着色具有权重|− 1+2+ min {|X|-1，k-2 }。|− 1,k − 2}.但是，|X| − 1，k− 2}= min {|X|，k−1}− 1;其中α k（D）≥|Y| + min {|X|，k-1}。一个弧-刺有向图是k-松散的，如果|X|<或者存在一个子集S<$X，|S|= k使得没有顶点y∈Y与S的每个顶点相邻，且S中至少有两个不同的顶点x u和x v使得{u，x u}和{v，x v}是独立集.在k-loose中，弧-刺有向图是k-紧的，如果它不是k-松的，即，|X| ≥ k且对于每个子集S <$X，|S|= k或者：(a) 存在y∈Y：S<$N（y）或(b) 存在x∈S使得N（u）<$S=N（v）<$S=S− {x}。在引理2.4中，我们证明了k-松弛弧-刺有向图存在类似于[9，引理1]的然而，请注意，这里给出的弧-刺有向图的k -loose的概念与[9]中给出的刺有向图的k-loose的概念不同。需要k-loose的不同定义作为一种手段，以保证弧-刺有向图存在[9]中引理1和引理3的完美类似物[9，引理3]的类似物是引理2.8。引理2.4如果D[X，Y]是k-松弧-刺有向图，则：(i) α k（D）≥| Y |+min{|X|，k}，并且(ii) πk（ D）≤ αk（ D）。证明：π k（D）≤|Y| +min {|X|，k}，因为这是规范划分的k -范数（即使当D是脊时，也存在具有这样的k -范数的路径划分）。此外，还记得标准k-偏着色|Y |+ min {|X|，k − 1}（即使D是spine，也有一个k-部分着色具有这样的权重）。如果|X|1，否则P不是无电荷的。那么，顶点x i−1存在，弧（x i−1，yi−1）也存在，这是由i的极小性和引理2.7决定的。第2.9章又来了我们得出yi−1/=yi，yi−1/=u和yi v。为了结束基本情况，令SJ={xi−1，xj+1}。Sinceyj+1v和yi−1/=u，xj+1和xi−1都不能同时与u和v相邻;因此，（b）不能为J。然后，（a）对于SJ成立，并且存在顶点YJ使得它与SJ的两个顶点相邻。通过选择j，我们有（YJ，xj+1）∈A（D）。因此，yJyj，因为P是无电荷的。通过对称推理，（xi−1，YJ）∈A（D）且ndyj=/yi。 根据权利要求2.9，我们有yJ=/u和yJv。顶点yi和yj可以是不同的。首先考虑一下这种情况yiyj. 则路径P1=Pxi−1<$（xi−1，yJ，xj+1）<$xj+1P和P2=（yi，xi）<$xiPxj<$L.R. Yoshimura等人/理论计算机科学电子笔记346（2019）735743y′X1xi−1Xixt−1Xtxt+1XJxj+1X轴P1yJytP2y′X1xi−1Xi...XJxj+1xP1yiyjP2图4. yi/=yj。 路径P1=Pxi−1<$（xi−1，y′，xj+1）<$xj+1P和P2=（yi，xi）<$xiPxj<$（xj，yj）。图5.yi=yj且（xt，yt）∈A（D）.路径P1=Pxt−1<$（xt−1，y′，xj+1）<$xj+1P，P2=（yt，xt）（xj，yj）满足条件（i）至（iv）。（xj，yj）满足条件（i）tthrough（iv）（图4）。我们可以假设yi=yj 。 我们现在可以看到，x xt是一个相同的值，i ≤ t ≤ j，与yJ不相邻。要做到这一点，假设相反。然后，根据引理2.2，由于（yJ，xj+1）∈A（D），我们也必须有arc（yJ，xi−1）∈A（D）;这与i的选择是矛盾的。因此，选择i≤t≤j，使得t是最小值，并且x t不与yJ相邻。根据引理2.7，有某个顶点yt∈Y与xt相邻。 由于y t与toxt相邻，显然yt/=yJ。 我们现在将表明yt不同于yi=yj。假设yt=yi=yj是Y中的任意一个vertxinYadjace nttooxt。回想一下yii=u和yji=v。 LetSt={xt，xj+1}。Sinceyiu和yjv，（a）请稍等因此，（xj，yj=yt）∈A（D）且nd（yt，xj+1）∈A（D）;所以P有一个曲折，一个矛盾。 我们由此推导出yt不同于yi=yj。若（xt，yt）∈A（D），则路径P1=Pxi−1<$（xi−1，yJ，xj+1）<$xj+1P，P2=xt+1Pxj<$（xj，yj=yi，xi）<$xiPxt<$（xt，yt）满足条件（i）t（iv）（图5）。如果（y t，x t）∈A（D），注意，通过选择t，我们知道yJ与（x i−1，.中的每个顶点相邻。x t−1）。此外，由于（xi−1，yJ）∈A（D），由引理2.2（xt−1，yJ）∈A（D）。那么，路径 P1= Px t−1<$（x t−1，yJ，x j+1）<$x j+1P和 P2=（yt，xt）<$xtPxj<$（xj，yj）满足条件（i）through（i v）（图6）。最后，基本情况k= 2的证明完成。假设k>2。根据引理2.5，存在某个顶点x j∈V（P）使得存在某个弧（xj ， yj ）∈A（D），对于yj∈Y且j≥k−1。 在所有子弧中，选择j最大的弧a j。由于P是无顶点的，我们知道j< l，因此P中有一个顶点x j+1。令XJ= V（Px j），令744L.R. Yoshimura等人/理论计算机科学电子笔记346（2019）735−/∈JJJ∈J−y′X1xi−1Xixt−1Xtxt+1XJxj+1X轴P1yJytP2图6.yi=yj且（yt，xt）∈A（D）.路径P1=Pxt−1<$（xt−1，y′，xj+1）<$xj+1P，P2=（yt，xt）（xj，yj）满足条件（i）至（iv）。YJ={yJ：yJ∈Y且yJ与xj+1相邻}，如果{u，v}中至少有一个与xj+1相邻;YJ={yJ：yJ∈ Y且yJ与x j+1}相邻<${u}，否则。注意，yj/∈YJ为yj/=uby，且P是无边界的。 此外，如果Y的某个顶点不与x j+1相邻，则该顶点在这种情况下是u和v Y。设DJ=D[XJ，YJ]，设PJ=Pxj。若YJ是稳定集，则DJ是一个有向棘图，并且由于{u，v}中至少有一个顶点在YJ中，所以可以证明DJ是（k1）-紧的. 根据[9，引理3]，DJ具有满足上述条件（i）至（iv）的路径P1 j和P2 j。现在考虑Y J包含u和v的情况。我们将证明PJ在DJ中是无边界的。假设相反。然后，由于P在D中是无弧的，这意味着对于某个顶点y∈YJ ，存在弧（xj−1，u）∈A（DJ）或（xj，y）∈A（DJ）。然而，如果（xj−1，u）∈A（DJ），由于v∈YJ，则（v，xj+1）∈A（D）和P在D中不是无边界的，这是一个矛盾。类似地，如果对于某个顶点y∈YJ，（xj，y）∈A（DJ），由于根据权利要求2.9，y u，我们推出（y，xj+1）∈A（D）. 但是P在D中不是无负矛盾我们现在证明DJ是一个（k-1）紧弧-刺有向图。设SJ<$XJ是任意k−1个顶点的集合;由引理2.5我们知道j≥k−1。 设S=SJ<${xj+1}是D的k个顶点的集合.由于D是k紧的，所以（a）或（b）对S成立. 如果（a）对D中的S成立，那么很容易看出（a）对S也成立在DJ.所以假设（b）对D中的S成立。我们知道{u，v}∈YJ，因此（v，xj+1） A（D）。因此，S中唯一不与u和v相邻的顶点是SJ的某个顶点，并且（b）对DJ中的SJ成立（图7）。因此，我们证明了DJ是一个（k1）-紧弧-刺有向图（即使YJ是稳定的，这个断言也成立），而PJ是无弧的。 通过应用于DJ和PJ的归纳假设，在DJ中存在满足条件（i）至（iv）的路径P1 j和P2 j。在不失一般性的情况下，假设ter（P1j）= xj和ter（P2j）= YJ，其中yj∈YJ.设f（YJ，xj+1）∈A，我们可以把P1=P1J<$（xj ，yj ）和P2= P2J<$（ YJ，xj+1）<$xj+1P作为D的路.条件（i）在这种情况下成立，因为P1J和P2J通过归纳推理是不相交的，并且既不是顶点yj，L.R. Yoshimura等人/理论计算机科学电子笔记346（2019）735745X′X1X2...XJxj+1...yJuv...Y′图7.（b）对于D′中的S′成立。xj+1P的任何顶点都是DJ的顶点。当（YJ，xj+1）/∈A时，确定YJ=u且v/∈YJ。所以我们可以取P1=P1J<$xjP和P2=P2J<$（u，v）作为D.条件（i）在这种情况下也成立。最后，我们证明了P1和P2在任一情况下都满足条件（i）到（iv条件（iii）和（iv）显然成立。（二）条件成立，因为|P1J|+的|P2J|=j + k的归纳假设。因此|+的|P 2|为|P 1 j|+的|P2J|+的|X|− j +1 =| X|+ k +1|+ k +1证据就完整了Q定理2.10设D [X，Y]是弧-刺有向图。 则π k（D）≤ α k（D）.证明我们可以假设D是k紧的，否则结果由引理2.4得出。我们知道α k（D）≥|Y| + min {|X|，k-1}。由于D是k紧的，我们有定义，|X|因此，α k（D）≥|Y |+ k − 1。 假设λ（D）>|X|.由于λ（D）>|X|，则D中存在路径P，使得|P|为 |X| +1 。 设 P=P<${ （ v ） ： v∈/V （ P ） }.显 然 ， P 是 D的 路 径 划 分 ，|P|k=min{|P| ， k}+|Y|−1=|Y|+k−1 。 因 此 ， πk （ D ） ≤|P|K=|Y|+k−1≤αk（D），结果如下。因此，我们可以假设λ（D）= |X|.设P =（x1，x2，...，xl）是D [ X ]中的Hamilton路。由于λ（D）= |X|，我们有P是D中的最长路;因此，它必须是无边界的。根据引理2.8，D中存在不相交的路P1和P2，使得|P1|+的|P2|为|X|+ k + 1。注意|P i|>k，对于i=1，2，否则P3−i将大于|X|.LetP={P1，P2} <${（y）：y∈/V（P1）<$V（P2）}. 很容易看出P是D中的一个路径划分。P的k范数为|k = m i n {|P1|，k } + m i n{|P2|，k }+|Y|− k − 1=|Y|+ k − 1。|+k−1. 因此，πk（D）≤|Y|+k−1，结果如下。Q3结论Sambinelli、Nunes da Silva和Lee采用了证明分裂有向图的Linial对偶猜想的技巧来证明有向脊图的Linial猜想。在本文中，我们能够将同样的技术应用到一个超类的脊椎有向图。证明的最重要的陈述是引理2.8，其归纳证明的断言和结构与[9，引理3]的断言和结构具有相似的元素。尽管脊和弧-脊有向图在结构上非常相似，但弧-脊有向图的基本情况的证明碰巧比脊有向图的基本情况复杂得多。现在很难理解这代表什么。直觉告诉我们，也许可以调整746L.R. Yoshimura等人/理论计算机科学电子笔记346（2019）735本文证明了有向刺图的超类比弧刺图的超类结构更复杂。引用[1] Dilworth，Robert Palmer，A Decomposition Theorem for Partially Ordered Sets，数学年鉴. 51（1950），161[2] Tilbor Gallai and Arthur Norton Milgram，Verallgemeinerung eines graphentheoretischen SatzesvonR′edei，ActaSciMath. 21（1960），181-186.[3] Curtis Greene和Daniel J. Kleitman，Sperner k族的结构，组合理论杂志，A辑。20（1976），41[4] Irith Ben-Arroyo Hartman Hartman，Fathi Saleh，Daniel Hershkowitz，On Greene[5] Michael Saks，偏序集的k-饱和分拆存在性的一个简短证明，数学进展33（1979），207[6] 李明，有向图的格林-克莱特曼定理，组合理论杂志，A辑。30（1981），331[7] Claude Berge，有向图的k-最优划分，欧洲组合数学杂志3（1982），97-101.[8] Eli Berger和Irith Ben-Arroyo Hartman。证明BergeEuropean Journal of Combinatorics，29（1）（2008），179[9] MayconSambinelliandCandidaNunesdaSilvaandOrlando Lee，OnLinial340（2017），851[10] 梅康·桑比内利图和有向图中的划分问题。博士论文，计算研究所，Unicamp，坎皮纳斯，巴西，2018年。用葡萄牙语
我的内容管理
展开
