Clique minors in graphs with a forbidden subgraph
Clique minors in graphs with a forbidden subgraph
复制标题
带有禁止子图的图中的小集团未成年人
DOI：
10.1002/rsa.21038
复制
发表时间：
2021
影响因子：
1
通讯作者：
Sudakov, Benny
中科院分区：
文献类型：
--
作者：
Bucić, Matija;Fox, Jacob;Sudakov, Benny
经典的Hadwiger猜想可以追溯到20世纪40年代，它指出任何色数图至少有a次图团。Hadwiger猜想是一类研究得很好的问题的一个例子，这类问题询问在具有某些限制的图中可以保证多大的团子。这种类型的一个问题是问什么是最大的尺寸团未成年人在一个图上的顶点的独立数在大多数。如果Hadwiger猜想成立，就意味着存在一个有序的小集团。Kühn和Osthus以及Krivelevich和Sudakov的结果意味着，如果另外假设对于某些二部图H，Gis H-free，那么可以找到多项式更大的团子式。最近，Dvokiák和Yepremyan将其扩展到无三角形图，回答了Norin的一个问题。我们完成的图片，并表明，这是真的任意graphH，回答一个问题的Dvokiák和Yepremyan。特别是，我们证明了任何自由图都有一个团子的顺序，一些常数只依赖于。这个结果中的指数在项前面紧到一个常数因子。
The classical Hadwiger conjecture dating back to 1940s states that any graph of chromatic number at leastrhas the clique of orderras a minor. Hadwiger's conjecture is an example of a well‐studied class of problems asking how large a clique minor one can guarantee in a graph with certain restrictions. One problem of this type asks what is the largest size of a clique minor in a graph onnvertices of independence number at mostr. If true Hadwiger's conjecture would imply the existence of a clique minor of order . Results of Kühn and Osthus and Krivelevich and Sudakov imply that if one assumes in addition thatGisH‐free for some bipartite graphHthen one can find a polynomially larger clique minor. This has recently been extended to triangle‐free graphs by Dvořák and Yepremyan, answering a question of Norin. We complete the picture and show that the same is true for arbitrary graphH, answering a question of Dvořák and Yepremyan. In particular, we show that any ‐free graph has a clique minor of order , for some constant depending only ons. The exponent in this result is tight up to a constant factor in front of the term.
登录
查看更多内容
关于 Hadwiger 与稳定性数之间的关系
影响因子：
0.8
作者：
Frédéric Maffray;H. Meyniel
通讯作者：
H. Meyniel
图小结构理论的新工具和结果
DOI：
--
发表时间：
2015
期刊：
Surveys in Combinatorics
影响因子：
--
作者：
S. Norin
通讯作者：
S. Norin
扩展图中的未成年人
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
Michael Krivelevich;B. Sudakov
通讯作者：
B. Sudakov
打破无 K 小调着色图的简并障碍
影响因子：
1.7
作者：
S. Norin;Zi
通讯作者：
Zi
DOI：
10.1017/s0305004100061521
发表时间：
1984
影响因子：
0.8
作者：
A. Thomason
通讯作者：
A. Thomason