≤≤可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）511-521www.elsevier.com/locate/entcs一个边着色问题Carlos Hoppen1InstitutodeMatema'ticaeEst'ısticaUniversidadeFederal do Rio Grande do Sul PortoAlegre，BrazilHanno Lefmann2Fakultaütfur？rInformatik，德国开姆尼茨理工大学摘要我们考虑一个问题的多色版本，最初是由Erd Prosos和Roths Child提出的。 对于正整数n和r，我们寻找允许最大数量的r-边着色的n -顶点图，其中没有三角形的副本，正好有两种颜色出现。 事实证明，对于2R12种颜色，n次极大的n阶完全二部图，它具有平衡二分性（n-阶三角形的图）产生最大的此类着色数，并且此图具有此性质是唯一的。关键字：边着色，Tur′an问题，ErdBronos-Rothschild问题1引言和主要结果这篇论文关注的是一个最初由ErdEkosos和Roths child[9]提出的问题的多色版本。他们的问题的动机在于Well-known Tur′an问题，其中给定一个整数n和一个图F，w∈k，求n -顶点图G中的最大边数ex（n，F），使得G不包含F作为子图. 一个不含F的图称为F-自由图，一个具有ex（n，F）边的无F的n-顶点图称为F-极值图.Turran[22]解决了当F=Kl+1是（l +1）个顶点上的完全图时的所有问题. 他证明，对于所有正整数n和l ≥ 2，任何1电子邮件：choppen@ufrgs.com.br2电子邮件：Lefmann@Informatik.TU-Chemnitz.de3本工作部分由C oorden acampaigndeA perve icampaign ntodePessoaldeN′pervelSu perior（CAPES）和DAAD通过Probral（CAPES程序88881.143993/2017-01和DAAD 57391132）提供支持。第一次，thora cn o acknowledgethesupportsofCNPq308054/2018-0），ConselhoNacionaldeDese nvolvime ntoCient′ficco e Tecno l′ogico.https://doi.org/10.1016/j.entcs.2019.08.0451571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。512C. Hoppen，H.Lefmann/电子笔记在理论计算机科学346（2019）511Kl+1-极图与图的拓扑图Tl（n）同构，Tl（n）是n -顶点上的完全l-部图，其部V={V1， . ，Vl}是最佳的，也就是说，|≤| VJ|对于所有i，j ∈ [ l ] = { 1，.|+ 1fora ll i,j∈[l]={1, . . . ，l}。特别地，ex（n，K3）=[n/2] ·[n/2|. 这是一个很好的解决问题的方法，我们参考[12]（以及其中的参考文献）了解更多信息。Erdosos和Roths的定理证明了n维顶点图的边着色，其性质是每个色类都是F-free的.他们想知道是否任何n-顶点图将承认更多这样的着色比相应的F-极值图。注意n-顶点F-极值图允许rex（n，F）着色，因为它们的边集可以任意着色.确切地说，Erdos和Rothschild猜想无Kl+1的2-染色的数目由Tl（n）最大化. Yuster [23]在l=2且n≥ 6时证明了这个猜想。Alon，Balogh，Keevash和Sudakov [2]证明了，对于r∈ {2，3}，n≥n0，其中n0是依赖于r和l的常数，图Tl（n）对于Kl+1-freer-染色的个数也是最优的. 然而，他们也提供了一个结构，表明Tl（n）对于任何r ≥4都不是最优的，但没有表征达到极值的图。 Pikhurko和Yilma [20]确定了r=4和l∈ {2，3}的极图。与Staden[19]一起，他们还推广了原ErdEscheros-Roths child问题，并证明了它总是存在一个完全多部图的极值解（然而，他们的证明并没有解决它是否必然是平衡的）。此外，他们定义了一个优化问题，其解决方案产生一个完全的多部图，其着色数量接近最大值。Balogh[3]是第一个考虑r-着色的人，它避免了图F以非单色方式着色Hoppen和Lefmann[15]以及Benevides，Hoppen和Sampaio[6]研究了一个类似的问题，他们考虑了图的边着色，避免了具有指定模式的F的副本。给定一个图F和r≥1个色数，F的r-模式P是它的边集至多分成r类的划分，如果G不包含F的一个副本，其中由染色诱导的边集的划分与P同构，则称图G的边染色是（F，P）-free的。例如，如果F=K3，有三种可能的模式：单色模式PM（所有的边都在同一个类中），彩虹模式PR（每个类都是单元素）和双色模式P2（有两个类，一个是单元素，另一个是基数2）。很明显，原始的ErdBronos-Rothschild问题正是在n-顶点图中找到最大数量的（F，PM）-free着色的问题对于ErdScholos-Roths child问题的这个多色版本的形式状态，固定一个正整数r和一个图F，设P是F的一个模式。设Cr，F，P（G）是图G的所有（F，P）-自由r-染色的集合.我们写cr，F，P（n）=max{|Cr，F，P（G）|：|V（G）|=n}，我们证明了n-顶点图G是（F，P）-外图，如果|Cr，F，P（G）|=cr，F，P（n）. 本文的主要目的是研究2-色模式P2的（K3，P2）-极图.关于K3的模式P，以下是已知的。 如上所述，C. Hoppen，H.Lefmann/电子笔记在理论计算机科学346（2019）5115133216 = 274 = 273 .第三章。32图T2（n）是单（K3，PM）-极图，其中r=2，n≥6（见[23]），r = 3，n≥n0（见[2]，[14]）.此外，当r= 4，n≥n0时，图T4（n）是单（K3，PM）-极图（见[20]）.据我们所知，r≥5的极图是未知的。对于彩虹模式PR，完全图Kn平凡地是r= 2的单（K3，PR）-极图当r≥ 5时，Odermann和目前的作者[16]证明了：当n ≥ n 0时（当r ≥ 10且n ≥ 5时），Tur′an图T2（n）是单（K3，PR）-极图.最近，Balogh和Li [4]证明了完全图Kn和Tur′an图T2（n）分别是r = 3和r = 4的单（K3，PR）-极图.在[5，6，10，16]中也得到了近似结果。对P2模式知之甚少.文[3]的工作证明了当r = 2，n ≥ n 0时，Turan图T2（n）是（K3，P2）-极值图. 文[6]的结果证明了：对任意r≥3，其中一个极图总是完全多部图（见[6，定理1.1]），且当r=3，n≥n0时，T2（n）是s（K3，P2）-极图（见[6，定理1.3]）.另一方面，设r = 27，并考虑将颜色集合i n划分为三个集合C1，C2，C3，其中r |C1|为|C2|为|C3|=9。我们将给顶点集被划分为V1<$··<$V4的4部图T4（n）着色如下（为简单起见，假设n可被4整除）。V1和V2之间以及V3和V4之间的边在C1中被分配颜色;V1和V3之间以及V2和V4之间的边在C2中被分配颜色;V1和V4之间以及V2和V3之间的边在C3中被分配颜色。显然，T4（n）中的任何三角形都必须是彩虹，因此这会产生C27，K3，P2（T4（n））中的着色。此外，以这种方式产生的着色的数量等于6·n2n2ex（n，K）由于T4（n）的着色还有许多其他的方法（例如，改变C1，C2，C3的选择），我们得 出 cr，K ，P（n）>rex（n ， K3 ） 的 结 论，因此当r = 27 时 ， Turr′an图不是（K3，P2）-极值图.实际上，一个类似的分析表明，对所有r≥27，T4（n）比T2（n）允许更多的（K3，P2）-free染色我们认为，对所有r≤26，至少对n≥n0，T2（n）是（K3，P2）-极值.本文利用正则引理结合线性规划方法给出了这方面的一个部分结果。定理1.1设P2是K3的模式，且2≤r≤12个。 则存在n0使得对于每个n ≥ n0和每个n-顶点图G，我们有|≤rex（n，K3）. |≤ rex(n,K3).此外，等式成立当且仅当G同构于双顶点Tur'angraphT2（n）。正如我们将在下面看到的，根据[17，引理3.1]，为了证明定理1.1，需要证明下面的稳定性结果，该结果表明任何具有"大“着色数的n-顶点对于一个图G=（V，E）和一个子集W<$V，我们写eG（W）来表示G的边数，其中9514C. Hoppen，H.Lefmann/电子笔记在理论计算机科学346（2019）511i=1两个端点W。如果所考虑的图G从上下文来看是明显的，我们简单地写e（W引理1.2设2 ≤r≤ 12是固定的。对于所有δ> 0，存在n0，具有以下性质。 若G =（V，E）是一个n> n0顶点的图，且至少有rex（n，K3）个不同的（K3，P2）-free r-染色，则存在其顶点集的一个划分V= W1<$W2，使得eG（W1）+eG（W2）≤δn2.注意，引理1.2直接意味着，|Cr、K3、P2（G）|≤rex（n，K3）+o（n2）对于r∈ {2，...， 12}。在本文的其余部分，我们将讨论引理1.2证明中的主要内容。值得一提的是，在过去的几年里，对于集合系统、幂格和自由和集等几种组合结构的Erd-Rothschild问题，有很多研究[7，8，13]。2主要成份我们首先观察到，由于Hoppen，Lefmann和Odermann [ 17 ]的先前结果，引理1.2的稳定性蕴涵定理1.1。[17]的作者定义了下面的稳定性概念。定义2.1设F是一个图，其色数χ（F）=1+ 1≥ 3，设P是F的一个模式。 对（F，P）满足颜色稳定性性质，一个正整数r，如果，对于每个δ >0，存在n0，具有以下性质。 如果n> n0且G是一个n-顶点图使得|Cr，F，P（G）|≥ rex（n，F），则有存在一个划分V（G）=V1<$ ··<$Vl，使得εG（Vi）≤δn2.然后证明了 对 于满 足 色 稳 定性 的 完 全 图的 一 类 模 式， 即 存 在 顶 点v 使 得与v关联的所有边属于不同类的模式，Tur′an图Tl（n）是使cr，K_n+1，P（n）最大化的任意n-顶点图. 这种类型的图案在当地被称为彩虹。请注意，双色三角形是局部彩虹。引理2.2[17，引理3.1]设l ≥ 2且P是Kl+1的局部彩虹模式，使得对于正整数r>e（l+1），（Kl+1，P）满足定义2.1的色稳定性性质。 则存在n0使得每个阶n>n0的图至多有rex（n， Kl+1）个不同的（Kl+1， P）-自由边染色. 此外，n个顶点上的着色数为rex（n，K_n+ 1）的唯一的图论是图朗图论T1（n）.他们还指出，在禁止图是三角形的情况下，该引理陈述中的下界r > e（l+ 1）可以替换为r≥3。由于引理1.2建立了2色三角形满足3≤r≤ 12的色稳定性，定理1.1如下。C. Hoppen，H.Lefmann/电子笔记在理论计算机科学346（2019）511515至多ε。 对（Vi，Vj）中的任意一个都不是ε-正则的.2.1正则引理我们的引理1.2是基于Szeme r'ediRegulari yLemma[21]。 设G=（V，E）是一个图，A和B是V（G）的两个不相交子集. 如果A和B是非空的，定义A和B之间的边密度为：d（A，B）=e（A，B）、|一||B|其中e（A，B）是一个端点在A中而另一个端点在B. 当ε >0时，称对（A，B）为ε-正则的，如果对每个X<$A和Y<$B，满足|X|>ε|一|和|Y|>ε|B|，我们有一个|ε。|<ε.集合V的公平划分是将V划分为成对不相交的类V1， . ，Vm几乎相等的大小，即， ||Vi| −|VJ||对于所有i，j∈[m]，≤ 1。 将G 的顶点集V公平划分为类V1，. V m称为ε-正则的 ，如果M2我们现在陈述一个正则引理的（彩色）版本，可以在[18]中找到。引理2.3对于每个ε > 0和每个整数r，存在M=M（ε，r）使得以下性质成立。 若n>M 阶 图 G 的 边 是 r- 着 色 的 E （ G ） = E1<$···<$Er ， 则 存 在 顶 点 集 V （ G ） = V1<$··<$Vm的一个划分，其中1/ε ≤ m ≤ M，它关于图Gi=（V，Ei）同时是ε-正则的，对所有i∈ [r].V（G）的一个划分V1<$··<$Vm（如引理2.3）称为多色ε-正则划分. 当η> 0时，我们可以定义一个与此划分相关联的多色簇图H（η）：顶点集为[m]，e={i，j}是H（η）i的边，如果{Vi，Vj}对每个颜色c ∈ [ r ]都是G中的正则对，且对某个颜色c∈[r] i是η -稠密的。每个边e都被分配了一个列表L e，其中包含了它是η -稠密的所有颜色，|Le| 对多色簇g_H（η）中的每条边≥ 1。给定一个着色图F，我们说一个多色簇图H包含F如果H包含F的一个拷贝，其中F的每条边的颜色包含在H中相应边的列表中。更一般地说，如果F是一个具有颜色模式P的图，我们说H包含（F，P），如果它包含F的一些具有与P同构的模式的着色副本。结合这个定义，我们可以得到下面的嵌入结果。 这个结果的证明来自于诸如密钥引理[18]的证明中的论证。引理2.4对每个η> 0和所有正整数k和r，存在ε=ε（r，η，k）> 0和一个正整数n0（r，η，k），该正整数n0（r，η，k）具有下列性质。 设G是一个n> n0顶点的r-着色图，其多色ε-正则划分V = V1···Vm定义了多色簇图H = H（η）. 设F是t≤r个类上具有指定颜色模式P的固定k-顶点图。如果H包含（F，P），则图G也包含（F，P）。516C. Hoppen，H.Lefmann/电子笔记在理论计算机科学346（2019）511Σi=1.Σαn≤≤22M2·4·=m≤εn≤2·n2.2稳定性本文的另一个基本工具是图的稳定性结果利用Fuéredi[11]给出的接收定理将是方便的。定理2.5设G =（V，E）是m 个 顶 点 的 Kk+1-free图.如果|E|为ex（m，K k+1）− t，则存在一个划分V = V1<$. 其中ke（V i）≤t。我们还使用了Alon和Yuster [1]的简单引理。引理2.6设G是m个顶点的二部图，其划分为V（G）= U1<$U2且至少有ex（m，K3）−t条边。 如果我们给G增加至少3t条新边，那么在所得到的图中存在K3的一个拷贝，它恰好有一条新边，连接K3在同一类Ui中的两个顶点。3引理1.2的证明在本节中，我们提供引理1.2的证明的草图。固定号码r∈ {2，.，12}的颜色和δ >0。为了避免案例分析，我们集中在情况r≥ 6 4。有远见地，我们考虑辅助常数η>0和η >0，使得n<δ，rrη+h（rη）<14rM（r）δ而η<2R、（1）其中M（r）在（11）中定义，h（x）= −xlog2x−（1−x）log2（1−x），其中h（0）=h（1）=0，是[0， 1]中的熵函数。 众所周知的是.n ≤ 2H（α）n0≤α≤ 1/ 2。令ε=ε（r，η，3）>0满足引理2.4中的假设，并且不失一般性地假设ε η/2.修正由引理2.3给出的M = M（r，ε）。设Δ是G=（V，E）的r-边染色，且不含2-着色三角形.根据引理2.3，存在着色图的多色ε-正则划分V = V1<$··<$Vm，其中1/ε mM.或each颜色，这里t至多是ε。关于分拆的m-非正则对V=V1<$··<$Vm，因此至多r·ε·。我...n=2rεn2（2）第二章G的边包含在关于某种颜色的不规则对中。此外，最多.n2n2M2η2≤≤m·（三）C. Hoppen，H.Lefmann/电子笔记在理论计算机科学346（2019）5115174 2≤r≤ 5的情形可以用类似的论证来证明。518C. Hoppen，H.Lefmann/电子笔记在理论计算机科学346（2019）511rηn2.Σ⎞()⎞()2^2M≤ 2·其中m≥1/ε.最后，使得e在Vi和Vj之间的颜色密度小于ηbe的端点在不同类Vi和Vj中的边e的数目至多为r·η·。我...nn=2rηn=2.（四）使用（2），（3）和（4）给出这三种类型的至多rηn2条边，它们可以在至多n2的方式请注意，这组边可以着色为最r rηn2 不同的方式。设H=H （ η ） 是与划分 V=V1···Vm 相 关 联 的 多 色 簇 图 .L e tEj （ H ） ={e∈E（H）：|Le|=j}和ej（H）=|Ej（H）|，j∈[r]. G的r-边染色的数目，产生划分V=V1···Vm和多色簇图H，上界为n2rηn2rηn2·⎛⎝n2Mjej（H）h（rη）n2rηn2·⎛⎝n2Mjej（H）.（五）j=1记住，在（1）中定义了一个常数。j=13.1必须存在一个多色簇图H，使得e r−3（H）+···+e r（H）≥ ex（m，K3）−<$m2.在证明这一主张之前，我们证明它意味着期望的结果。 设HJ是H的子图，其边集为Er−3<$··<$Er。根据定理2.5，存在一个划分U1<$U2=[m]，eH′（U1） +eH′（U2）≤μm.设H^e是HJ的一个二部子图，其二部划分为U1<$U2，最大值为边缘数。 注意，根据定理2.5，我们有e（H）≥ ex（m，K3）− 2 <$m2.我们主张e1（H）+···+er−4（H）≤6<$m2。否则，根据引理2.6，通过将E1···Er−4的边加到H^得到，将包含三角形使得恰好有一条边f1在E1<$··<$Er−4中。 设f2和f3为三角形的另外两条边，位于Er−3<$··<$Er。如果有一种颜色α∈Lf1<$（Lf2 <$Lf3），假设α∈Lf1<$Lf2，我们可以在Lf3中选择一个颜色β f =α，如下：|≥r − 3 ≥ 3。| ≥r−3 ≥3. 否则，设β∈Lf1，注意，|Lf2Lf3| ≤r−1，而|+的|Lf3|≥2 r − 6 ≥ r。| ≥2 r−6 ≥r. 所以有一个颜色α ∈Lf2<$Lf3，其中α/=β。 在两种情况下，这将导致一个2色三角形G引理2.4，矛盾。因此，H的两端都在同一集合U中.RRΣ·r≤2·rC. Hoppen，H.Lefmann/电子笔记在理论计算机科学346（2019）511519我最多7平方米。对于i ∈ { 1，2 }，L e tWi=<$j∈UVj。然后，通过选择η和η，我们有eG（W1）+eG（W2）≤rηn2+（n/m）2（eH（U1）+eH（U2））<δn2，（6）520C. Hoppen，H.Lefmann/电子笔记在理论计算机科学346（2019）511..Σ2 2- 是的-是的Σ−l=r−3j=2r−4Σj=2l=r−3j=2l=r−3Σ自由了22按要求为了结束引理1.2的证明，我们需要证明权利要求3.1。证据 （权利要求3.1的证明）对于一个矛盾，假设G的任何着色避免2色三角形导致多色聚类图H，其中e r−3（H）+···+e r（H） r，因此（12）不成立。规避该问题的一种可能的方式可以是对线性程序（11）包括附加的线性约束，以便减小最优值M（r）。F或例如，对于j=2， . ，[r/3π，letHJ]是多色图的子图簇图H（在引理1.2的证明中定义），具有边集Ej<$··<$Er−2j，并且确定HjJ的具有最大边数的二部子图BjJ，所以的|E（BjJ）|>>|E（HjJ）|/2=（ej（H） +· · ·+er−2j（H））/2（这是关于图的最大割的众所周知的事实）。设HJJJ是H的有边集的子图E（BjJ）<$Er−2j+1<$··< $Er。注意HjJJ是无三角形的，就像一个nysuch三角形我们有三条边f1，f2，f3，|Lfi|对于所有i，≥j≥2，且suchthatmaxi|Lfi| ≥r−2j+1≥2。根据鸽子洞原理，列表中的两个一个共同的颜色α，第三个列表具有颜色β意味着1α。 对于j=2， . ，[r/3]，th is2·（ej （H） +· ·+er−2j（H））+er−2j+1（H） +· · ·+er（H）≤ex（m，K3）.（十四）到目前为止，我们还没有成功地实现一个最佳的，是小于r的一些r≥13。可以想象，这样的方法可以扩展到所有r≤26，因为我们已经知道，二分图不可能是最优的r≥ 27。引用C. Hoppen，H.Lefmann/电子笔记在理论计算机科学346（2019）511525[1] N. Alon和R.Yuster，没有固定锦标赛的方向数，Combinatorica26（2006），1-16.[2] N. Alon，J. Balogh，P. Keevash，and B. Sudakov，The number of edge colorings with nomonochromatic cliques，Journal of the London Mathematical Society70（2）（2004），273-288.526C. Hoppen，H.Lefmann/电子笔记在理论计算机科学346（2019）511[3] J. Balogh，关于图的边着色数的一个注记，欧洲组合数学杂志27（2006），565[4] J. Balogh和L. Li，Gallai染色的典型结构及其极值图，arxiv：1812.07747.[5] J.O.巴特尔，F.S.贝内维德斯莫拉和我Sau，完全图的3-着色计数，arxiv：1805.06805。[6] F.S.贝内维德斯角Hoppen和R. M. Sampaio，Edge-colorings of graphs avoiding a prescribed coloringpattern，Discrete Mathematics240（9）（2017），2143[7] D.克莱门斯，S。Das和T. Tran，没有单色不相交对的着色，欧洲期刊of Combinatorics70（2018），99-124.[8] S.达斯河，巴西-地格列博夫湾Sudakov和T. Tran，没有单色k链的着色集家族，arXiv：1803.09573。[9] P. ErdBagos，概率方法在组合分析和图论中的一些新应用，第五届东南组合学、图论和计算会议论文集（佛罗里达大西洋大学，佛罗里达州博卡拉顿1974年）。第一次，不。X，Utilitas Math.（1974），39[10] 诉 Falgas-R avr y，K. O'Connell ， J. Str mberg和A. Uzzell ，多色容器和装饰图极限的熵，arXiv：1607.08152。[11] Z. Füredi，极图稳定性的一个推广，Simonovits从Szeme r ′ edi正则性得到的稳定性Journal of Combinatorial Theory，Series B115（2015），66[12] Z. Fouredi，和M. Simon ovits，Thehistoryofd egene rate（bi partite）ext remalg raphp roblems，ErdgeneosCentennial，Bolyai Society of Mathematics 25，Springer Verlag，2013，pp 169-213.[13] H. H an，和A. Jim′enez，Maximumnumberofsum-freecoloringsinfiniteabeliangroups，IsraelJournalofMathematics226（2）（2018），505[14] H. H an，和A. Ji m′enez，Impr ovedBoundontheMaximumNu mberofClique-FreeColoringswithTwo andThree Colors，SIAM Journal on Discrete Mathematics 32（2）（2018），1364-1368。[15] C. Hoppen和H.Lefmann，边缘着色避免与规定的颜色模式固定匹配European Journal of Combinatorics47（2015），75[16] C. Hoppen，H. Lefmann和K. Odermann，关于具有大量边着色避免的图彩虹三角形，EuropeanJournal of Combinatorics66（2017），168[17] C. Hop pen，H. Lefmann和K. Odermann，Arai nbowwErdBronos-Roths c hildproblem，SIAMJournalonDiscrete Mathematics31（2017），2647-2674。[18] J. Koml 'os和M. Simon ovits，Szeme r′edi正则引理及其在图论中的应用，Com binatorics，PaulErdErdosiseighty，Vol. 2（Keszthel y，1993），295-352，Bol y ai Soc. 数学螺柱：2，J'anosBol yaiMath. SOC.， 布达害虫，1996年。[19] O.皮 克 胡 尔 科 ， K 。 Staden 和 Z.B.Yilma ， ErdBronos-Rothsc hildproblemonedge-colouringswithforbidden monochromatic cliques ， Mathematical Proceedings of the CambridgePhilosophical Society163（2）（2017），341-356。[20] O. Pikhurko和Z. B.杨文，边4-着色的最大无K3和无K4数，北京大学学报of the London MathematicalSociety85（2）no.3（2012），593-615.[21] E. Szeme r′edi，Reg raphs，Prob l`emesco mbinatoirese t t tt heoriedesgraphes（Coll oq. 内部CNRS，Univ.Orsay，Orsay，1976），Colloq. Internat. CNRS，vol. 260，CNRS，Paris，1978，399-401.[22]P. Tur'an，Onanextremalproblemingraphtheory（匈牙利文），Matematikai'esFizikaiLapok48（1941），436[23] R. 图的边着色的个数，图论杂志21（1996），441
我的内容管理
展开
