Abstract
It is shown that there exists a positive c so that for any large integer m, any graph with 2m2 edges contains a bipartite subgraph with at least m2+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′e4/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 - 1996 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Mathematics