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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics