Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-17T18:23:01.831Z 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: [email protected])
XINGXING YU
Affiliation:
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 for i ∈ {1, 2, . . . k}, and , where e(Vi) denotes the number of edges with both ends in Vi and . This answers a problem of Bollobás and Scott [2] in the affirmative. Moreover, for i ∈ {1, 2, . . ., k}, which is close to being best possible and settles another problem of Bollobás and Scott [2].

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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