论文标题
集团未成年人在图形中带有禁忌子图
Clique minors in graphs with a forbidden subgraph
论文作者
论文摘要
经典的Hadwiger的猜想可以追溯到1940年代，即任何色度至少$ r $的图表都有订单$ r $的集团。 Hadwiger的猜想是一系列经过良好研究的问题的一个示例，询问一个集团的小数可以保证有一定限制的图表。这种类型的一个问题问，最多最多$ r $的$ n $ n $ n $ n $顶点$ n $顶点的集团小调的最大尺寸是多少。如果真正的Hadwiger的猜想将暗示存在$ n/α（g）$的集团少数集团。 Kuhn和Osthus，Krivelevich和Sudakov的结果暗示，如果有人假设$ G $是$ h $ $ h $ - 对于某些两部分图$ h $，那么人们可以找到一个多条件更大的集团小群。最近，Dvo夏克和Yepremyan将其扩展到了无三角形的图表，回答了Norin的问题。我们完成了图片，并表明，任意图$ H $也是如此，回答了Dvo红K和Yepremyan的问题。特别是，我们表明，任何$ k_s $ -free Graph都有一个集团$ c_s（n/α（g））^{1+ \ frac {1} {1} {10（s-2）} $，对于某些常数$ C_S $，仅根据$ s $。此结果中的指数紧密至$ \ frac {1} {s-2} $ term的恒定因素。
The classical Hadwiger conjecture dating back to 1940's states that any graph of chromatic number at least $r$ has the clique of order $r$ as 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 on $n$ vertices of independence number $α(G)$ at most $r$. If true Hadwiger's conjecture would imply the existence of a clique minor of order $n/α(G)$. Results of Kuhn and Osthus and Krivelevich and Sudakov imply that if one assumes in addition that $G$ is $H$-free for some bipartite graph $H$ then 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 graph $H$, answering a question of Dvořák and Yepremyan. In particular, we show that any $K_s$-free graph has a clique minor of order $c_s(n/α(G))^{1+\frac{1}{10(s-2) }}$, for some constant $c_s$ depending only on $s$. The exponent in this result is tight up to a constant factor in front of the $\frac{1}{s-2}$ term.
