Dense Induced Bipartite Subgraphs in Triangle-Free Graphs
Dense Induced Bipartite Subgraphs in Triangle-Free Graphs
复制标题
无三角形图中的密集诱导二部子图
DOI：
10.1007/s00493-019-4086-0
复制
发表时间：
2018
期刊：
影响因子：
1.1
通讯作者：
T. Tran
中科院分区：
文献类型：
--
作者：
Matthew Kwan;Shoham Letzter;B. Sudakov;T. Tran
在H -free图中寻找稠密诱导偶部子图的问题有着悠久的历史，早在30年前就由Erdens，Faudree，Pach和Spencer提出。本文在这个方向上得到了几个结果。首先证明了任何最小度至少为d的H -free图都包含一个最小度至少为c H log d /log log d的导出偶子图，从而几乎证实了Esperet，Kang和Jiassé的一个猜想，并证明了另一个猜想.作为对这一结果的补充，我们进一步得到了稠密无三角形图的最优界，并回答了Erdæs，Janson，Jubuczak和Spencer的一个问题。
The problem of finding dense induced bipartite subgraphs in H -free graphs has a long history, and was posed 30 years ago by Erdős, Faudree, Pach and Spencer. In this paper, we obtain several results in this direction. First we prove that any H -free graph with minimum degree at least d contains an induced bipartite subgraph of minimum degree at least c H log d /log log d , thus nearly confirming one and proving another conjecture of Esperet, Kang and Thomassé. Complementing this result, we further obtain optimal bounds for this problem in the case of dense triangle-free graphs, and we also answer a question of Erdœs, Janson, Łuczak and Spencer.
包装接近最优的 Ramsey R(3,t) 图
影响因子：
1.1
作者：
Guo, He;Warnke, Lutz
通讯作者：
Warnke, Lutz