Dense induced bipartite subgraphs in triangle-free graphs

Kwan MA, Letzter S, Sudakov B, Tran T. 2020. Dense induced bipartite subgraphs in triangle-free graphs. Combinatorica. 40(2), 283–305.


Journal Article | Published | English

Scopus indexed
Author
Kwan, Matthew AlanIST Austria; Letzter, Shoham; Sudakov, Benny; Tran, Tuan
Abstract
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 cH 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.
Publishing Year
Date Published
2020-04-01
Journal Title
Combinatorica
Volume
40
Issue
2
Page
283-305
ISSN
eISSN
IST-REx-ID

Cite this

Kwan MA, Letzter S, Sudakov B, Tran T. Dense induced bipartite subgraphs in triangle-free graphs. Combinatorica. 2020;40(2):283-305. doi:10.1007/s00493-019-4086-0
Kwan, M. A., Letzter, S., Sudakov, B., & Tran, T. (2020). Dense induced bipartite subgraphs in triangle-free graphs. Combinatorica. Springer. https://doi.org/10.1007/s00493-019-4086-0
Kwan, Matthew Alan, Shoham Letzter, Benny Sudakov, and Tuan Tran. “Dense Induced Bipartite Subgraphs in Triangle-Free Graphs.” Combinatorica. Springer, 2020. https://doi.org/10.1007/s00493-019-4086-0.
M. A. Kwan, S. Letzter, B. Sudakov, and T. Tran, “Dense induced bipartite subgraphs in triangle-free graphs,” Combinatorica, vol. 40, no. 2. Springer, pp. 283–305, 2020.
Kwan MA, Letzter S, Sudakov B, Tran T. 2020. Dense induced bipartite subgraphs in triangle-free graphs. Combinatorica. 40(2), 283–305.
Kwan, Matthew Alan, et al. “Dense Induced Bipartite Subgraphs in Triangle-Free Graphs.” Combinatorica, vol. 40, no. 2, Springer, 2020, pp. 283–305, doi:10.1007/s00493-019-4086-0.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1810.12144

Search this title in

Google Scholar