Bipartite subgraphs

Research output: Contribution to journalArticlepeer-review

77 Scopus citations

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 languageEnglish (US)
Pages (from-to)301-311
Number of pages11
JournalCombinatorica
Volume16
Issue number3
DOIs
StatePublished - 1996
Externally publishedYes

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