Name
Abstract | ||
|---|---|---|
For positive integers kï¾ź2 and m, let gkm be the smallest integer such that for each graph G with m edges there exists a k-partition VG=V1ï¾ź'ï¾źVk in which each Vi contains at most gkm edges. Bollobás and Scott showed that gkmï¾źmk2+k-12k22m+1/4-1/2. Ma and Yu posed the following problem: is it true that the limsup of mk2+k-12k22m-gkm tends to infinity as m tends to infinity? They showed it holds when k is even, establishing a conjecture of Bollobás and Scott. In this article, we solve the problem completely. We also present a result by showing that every graph with a large k-cut has a k-partition in which each vertex class contains relatively few edges, which partly improves a result given by Bollobás and Scott. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1002/jgt.22094 | Journal of Graph Theory |
Keywords | Field | DocType |
graph,max-cut,judicious partition | Integer,Graph,Combinatorics,Vertex (geometry),Infinity,Conjecture,Maximum cut,Mathematics | Journal |
Volume | Issue | ISSN |
85 | 3 | 0364-9024 |
Citations | PageRank | References |
0 | 0.34 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| liu | 1 | 195 | 21.38 |
| Qinghou Zeng | 2 | 7 | 1.57 |