More on the Bipartite Decomposition of Random Graphs

Noga Alon, Tom Bohman, Hao Huang

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

For a graph G = (V, E), let bp(G) denote the minimum number of pairwise edge disjoint complete bipartite subgraphs of G so that each edge of G belongs to exactly one of them. It is easy to see that for every graph G, bp(G) ≤ n − α(G), where α(G) is the maximum size of an independent set of G. Erdős conjectured in the 80s that for almost every graph G equality holds, that is that for the random graph G(n, 0.5), bp(G) = n − α(G) with high probability, that is with probability that tends to 1 as n tends to infinity. The first author showed that this is slightly false, proving that for most values of n tending to infinity and for G = G(n, 0.5), bp(G) ≤ n − α(G) − 1 with high probability. We prove a stronger bound: there exists an absolute constant c > 0 so that bp(G) ≤ n − (1 + c)α(G) with high probability.

Original languageEnglish (US)
Pages (from-to)45-52
Number of pages8
JournalJournal of Graph Theory
Volume84
Issue number1
DOIs
StatePublished - Jan 1 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • bipartite decomposition
  • random graph

Fingerprint Dive into the research topics of 'More on the Bipartite Decomposition of Random Graphs'. Together they form a unique fingerprint.

Cite this