Hostname: page-component-74656f9884-rngvg Total loading time: 0 Render date: 2026-11-06T10:08:14.081Z Has data issue: false hasContentIssue false
  • English
  • Français

Maximizing Several Cuts Simultaneously

Published online by Cambridge University Press:  01 March 2007

DANIELA KÜUHN  and
DERYK OSTHUS
DANIELA KÜUHN
Affiliation:
School of Mathematics, Birmingham University, Edgbaston, Birmingham B15 2TT, UK (e-mail: kuehn@maths.bham.ac.uk, osthus@maths.bham.ac.uk)
DERYK OSTHUS
Affiliation:
School of Mathematics, Birmingham University, Edgbaston, Birmingham B15 2TT, UK (e-mail: kuehn@maths.bham.ac.uk, osthus@maths.bham.ac.uk)
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.

Consider two graphs G1 and G2 on the same vertex set V and suppose that Gi has mi edges. Then there is a bipartition of V into two classes A and B so that, for both i = 1, 2, we have $e_{G_i}(A,B) \geq m_i/2-\sqrt{m_i}$. This gives an approximate answer to a question of Bollobás and Scott. We also prove results about partitions into more than two vertex classes. Our proofs yield polynomial algorithms.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 2 , March 2007 , pp. 277 - 283
Copyright
Copyright © Cambridge University Press 2006

References

[1]Alon, N. and Spencer, J. (2000) The Probabilistic Method, 2nd edn, Wiley-Interscience.CrossRefGoogle Scholar
[2]Bollobás, B. and Scott, A. D. (1993) Judicious partitions of graphs. Periodica Math. Hungar. 26 127–139.CrossRefGoogle Scholar
[3]Bollobás, B. and Scott, A. D. (1999) Exact bounds for judicious partitions. Combinatorica 19 473–486.Google Scholar
[4]Bollobás, B. and Scott, A. D. (2002) Problems and results on judicious partitions. Random Struct. Alg. 21 414–430.CrossRefGoogle Scholar
[5]Bollobás, B. and Scott, A. D. (2004) Judicious partitions of bounded-degree graphs. J. Graph Theory 46 131–143.CrossRefGoogle Scholar
[6]Edwards, C. S. (1973) Some extremal properties of bipartite subgraphs. Canadian J. Math. 25 475–485.CrossRefGoogle Scholar
[7]Edwards, C. S. (1975) An improved lower bound on the number of edges in a largest bipartite subgraph. In Proc. 2nd Czech. Symposium on Graph Theory, Prague, pp. 167–181.Google Scholar
[8]Fundia, A. D. (1996) Derandomizing Chebyshev's inequality to find independent sets in uncrowded hypergraphs. Random Struct. Alg. 8 131–147.3.0.CO;2-Z>CrossRefGoogle Scholar
[9]Kühn, D. and Osthus, D. (2003) Partitions of graphs with high minimum degree or connectivity. J. Combin. Ser. Theory B 88 29–43.CrossRefGoogle Scholar
[10]Motwani, R. and Raghavan, P. (1995) Randomized Algorithms, Cambridge University Press.CrossRefGoogle Scholar
[11]Papadimitriou, C. H. and Yannakakis, M. (1991) Optimization, approximation, and complexity classes. J. Comput. System Sci. 43 425–440.CrossRefGoogle Scholar
[12]Porter, T. D. (1992) On a bottleneck conjecture of Erdős. Combinatorica 12 317–321.CrossRefGoogle Scholar
[13]Porter, T. D. (1994) Graph partitions. J. Combin. Math. Combin. Comp. 15 111–118.Google Scholar
[14]Porter, T. D. (1999) Minimal partitions of a graph. Ars Combinatorica 53 181–186.Google Scholar
[15]Rautenbach, D. and Szigeti, Z. (2004) Simultaneous large cuts. Manuscript.Google Scholar
[16]Stiebitz, M. (1996) Decomposing graphs under degree constraints. J. Graph Theory 23 321–324.3.0.CO;2-H>CrossRefGoogle Scholar