Abstract | ||
---|---|---|
The vertices of any graph with m edges may be partitioned into two parts so that each part meets at least $$\tfrac{{2m}} {3}$$ edges. Bollobás and Thomason conjectured that the vertices of any r-uniform hypergraph with m edges may likewise be partitioned into r classes such that each part meets at least $$\tfrac{r} {{2r - 1}}$$ edges. In this paper we prove the weaker statement that, for each r 4, a partition into r classes may be found in which each class meets at least $$\tfrac{r} {{3r - 4}}$$ edges, a substantial improvement on previous bounds. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1007/s00493-014-2916-7 | Combinatorica |
Keywords | Field | DocType |
05c65 | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Constraint graph,Hypergraph,Partition (number theory),Mathematics | Journal |
Volume | Issue | ISSN |
34 | 5 | Combinatorica (2014) 34: 561 |
Citations | PageRank | References |
4 | 0.44 | 10 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
John Haslegrave | 1 | 29 | 5.74 |