UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Dense Induced Bipartite Subgraphs in Triangle-Free Graphs

Kwan, M; Letzter, S; Sudakov, B; Tran, T; (2020) Dense Induced Bipartite Subgraphs in Triangle-Free Graphs. Combinatorica , 40 (2) pp. 283-305. 10.1007/s00493-019-4086-0. Green open access

[img]
Preview
Text
induced-bipartite_final.pdf - Accepted version

Download (466kB) | Preview

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.

Type: Article
Title: Dense Induced Bipartite Subgraphs in Triangle-Free Graphs
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/s00493-019-4086-0
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery.ucl.ac.uk/id/eprint/10107226
Downloads since deposit
7Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item