Name
Abstract | ||
|---|---|---|
For a graph G = ( V , E ) , let ¿ ( 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, ¿ ( 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, i.e., that for the random graph G ( n , 0.5 ) , ¿ ( G ) = n - α ( G ) with high probability, that is, with probability that tends to 1 as n tends to infinity. Here we show that this conjecture is (slightly) false, proving that for all n in a subset of density 1 in the integers and for G = G ( n , 0.5 ) , ¿ ( G ) ¿ n - α ( G ) - 1 with high probability, and that for some sequences of values of n tending to infinity ¿ ( G ) ¿ n - α ( G ) - 2 with probability bounded away from 0. We also study the typical value of ¿ ( G ) for random graphs G = G ( n , p ) with p |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.jctb.2015.03.001 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
random graphs | Integer,Discrete mathematics,Graph,Combinatorics,Disjoint sets,Random graph,Bipartite graph,Independent set,Conjecture,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
113 | C | 0095-8956 |
Citations | PageRank | References |
1 | 0.39 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noga Alon | 1 | 10468 | 1688.16 |
| Tom Bohman | 2 | 250 | 33.01 |
| Hao Huang | 3 | 589 | 104.49 |