Hostname: page-component-74656f9884-g96k6 Total loading time: 0 Render date: 2026-11-10T08:53:55.903Z Has data issue: false hasContentIssue false
  • English
  • Français

Better Bounds for k-Partitions of Graphs

Published online by Cambridge University Press:  31 May 2011

BAOGANG XU  and
XINGXING YU
BAOGANG XU
Affiliation:
School of Mathematical Sciences, Nanjing Normal University, 1 Wenyuan Road, Yadong New District, Nanjing, 210046, China (e-mail: baogxu@njnu.edu.cn)
XINGXING YU
Affiliation:
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA (e-mail: yu@math.gatech.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let G be a graph with m edges, and let k be a positive integer. We show that V(G) admits a k-partition V1, . . . Vk such that $e(V_i)\leq \frac 1{k^2}m+\frac {k-1}{2k^2}(\sqrt{2m+1/4}-1/2)$ for i ∈ {1, 2, . . . k}, and $e(V_1, \ldots, V_k)\geq \frac{k-1}{ k} m +\frac{k-1}{ 2k}\sqrt{2m+1/4} +O(k)$, where e(Vi) denotes the number of edges with both ends in Vi and $e(V_1,\ldots, V_k)=m-\sum_{i=1}^ke(V_i)$. This answers a problem of Bollobás and Scott [2] in the affirmative. Moreover, $\binom{k+1}{ 2}e(V_i)+\frac k2\sum_{j\ne i}e(V_j)\le m + O(k^2)$ for i ∈ {1, 2, . . ., k}, which is close to being best possible and settles another problem of Bollobás and Scott [2].

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 4 , July 2011 , pp. 631 - 640
Copyright
Copyright © Cambridge University Press 2011

References

[1]Bollobás, B. and Scott, A. D. (1999) Exact bounds for judicious partitions of graphs. Combinatorica 19 473–486.Google Scholar
[2]Bollobás, B. and Scott, A. D. (2002) Problems and results on judicious partitions. Random Struct. Alg. 21 414–430.CrossRefGoogle Scholar
[3]Bollobás, B. and Scott, A. D. (2002) Better bounds for Max Cut. In Contemporary Combinatorics, Vol. 10 of Bolyai Society Mathematical Studies, János Bolyai Mathematical Society, pp. 185–246.Google Scholar
[4]Edwards, C. S. (1973) Some extremal properties of bipartite graphs. Canad. J. Math. 25 475–485.CrossRefGoogle Scholar
[5]Edwards, C. S. (1975) An improved lower bound for the number of edges in a largest bipartite subgraph. In Proc. 2nd Czechoslovak Symposium on Graph Theory, pp. 167–181.Google Scholar
[6]Scott, A. (2005) Judicious partitions and related problems. In Surveys in Combinatorics, Vol. 327 of London Mathematical Society Lecture Notes, Cambridge University Press, pp. 95–117.Google Scholar
[7]Porter, T. D. (1994) Graph partitions. J. Combin. Math. Combin. Comp. 15 111–118.Google Scholar
[8]Xu, B. and Yu, X. (2009) Judicious k-partitions of graphs. J. Combin. Theory Ser. B 99 324–337.CrossRefGoogle Scholar