---
_id: '9582'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Matthew Alan
full_name: Kwan, Matthew Alan
id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
last_name: Kwan
orcid: 0000-0002-4003-7567
- first_name: Shoham
full_name: Letzter, Shoham
last_name: Letzter
- first_name: Benny
full_name: Sudakov, Benny
last_name: Sudakov
- first_name: Tuan
full_name: Tran, Tuan
last_name: Tran
citation:
ama: 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
apa: 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
chicago: 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.
ieee: 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.
ista: Kwan MA, Letzter S, Sudakov B, Tran T. 2020. Dense induced bipartite subgraphs
in triangle-free graphs. Combinatorica. 40(2), 283–305.
mla: 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.
short: M.A. Kwan, S. Letzter, B. Sudakov, T. Tran, Combinatorica 40 (2020) 283–305.
date_created: 2021-06-22T06:42:26Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2023-02-23T14:01:45Z
day: '01'
doi: 10.1007/s00493-019-4086-0
extern: '1'
external_id:
arxiv:
- '1810.12144'
intvolume: ' 40'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1810.12144
month: '04'
oa: 1
oa_version: Preprint
page: 283-305
publication: Combinatorica
publication_identifier:
eissn:
- 1439-6912
issn:
- 0209-9683
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dense induced bipartite subgraphs in triangle-free graphs
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 40
year: '2020'
...