## 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 = V_{1} ∪ V_{2} such that both parts V_{1}, V_{2} 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 language | English (US) |
---|---|

Pages (from-to) | 329-346 |

Number of pages | 18 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 88 |

Issue number | 2 |

DOIs | |

State | Published - Jul 2003 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

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