### Abstract

It is shown that there exists a positive c so that for any large integer m, any graph with 2m^{2} edges contains a bipartite subgraph with at least m^{2}+m/2+c√m edges. This is tight up to the constant c and settles a problem of Erdos. It is also proved that any triangle-free graph with e>1 edges contains a bipartite subgraph with at least e/2+c′e^{4/5} edges for some absolute positive constant c′. This is tight up to the constant c′.

Original language | English (US) |
---|---|

Pages (from-to) | 301-311 |

Number of pages | 11 |

Journal | Combinatorica |

Volume | 16 |

Issue number | 3 |

DOIs | |

State | Published - Jan 1 1996 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Computational Mathematics

## Fingerprint Dive into the research topics of 'Bipartite subgraphs'. Together they form a unique fingerprint.

## Cite this

Alon, N. (1996). Bipartite subgraphs.

*Combinatorica*,*16*(3), 301-311. https://doi.org/10.1007/BF01261315