Maximum cuts and judicious partitions in graphs without short cycles

Noga Alon, Béla Bollobás, Michael Krivelevich, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

37 Scopus citations

Abstract

We consider the bipartite cut and the judicious partition problems in graphs of girth at least 4. For the bipartite cut problem we show that every graph G with m edges, whose shortest cycle has length at least r≥4, has a bipartite subgraph with at least m/2 + c(r)m r/r+1 edges. The order of the error term in this result is shown to be optimal for r = 5 thus settling a special case of a conjecture of Erdos. (The result and its optimality for another special case, r = 4, were already known.) For judicious partitions, we prove a general result as follows: if a graph G = (V, E) with m edges has a bipartite cut of size m/2 + δ, then there exists a partition V = V1 ∪ V2 such that both parts V1, V2 span at most m/4 - (1 - o(1))δ/2 + O( m) edges for the case δ = o(m), and at most (1/4 - Ω(1))m edges for δ = Ω(m). This enables one to extend results for the bipartite cut problem to the corresponding ones for judicious partitioning.

Original languageEnglish (US)
Pages (from-to)329-346
Number of pages18
JournalJournal of Combinatorial Theory. Series B
Volume88
Issue number2
DOIs
StatePublished - Jul 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Maximum cuts and judicious partitions in graphs without short cycles'. Together they form a unique fingerprint.

Cite this