Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 20, 2019 | Submitted
Report Open

Large subgraphs without complete bipartite graphs


In this note, we answer the following question of Foucaud, Krivelevich and Perarnau. What is the size of the largest K_(r,s)-free subgraph one can guarantee in every graph G with m edges? We also discuss the analogous problem for hypergraphs.

Additional Information

We would like to thank M. Krivelevich for bringing this problem to our attention and for sharing with us preprint 'Large subgraphs without short cycles' by F. Foucaud, M. Krivelevich and G. Perarnau.

Attached Files

Submitted - 1401.6711.pdf


Files (88.7 kB)
Name Size Download all
88.7 kB Preview Download

Additional details

August 19, 2023
October 18, 2023