






















For an integer $k\ge 2$, let $G$ be a graph with $m$ edges and without cycles of length $2k$. The pivotal Alon-Krivelevich-Sudakov Theorem on Max-Cuts states that $G$ has a bipartite subgraph with at least $m/2+Ω(m^{(2k+1)/(2k+2)})$ edges. In this paper, we present a bisection variant of it by showing that if $G$ has minimum degree at least $k$, then $G$ has a balanced bipartite subgraph with at least $m/2+Ω(m^{(2k+1)/(2k+2)})$ edges. It not only answers a problem of Fan, Hou and Yu in full generality but also enhances a recent result given by Hou, Wu and Zhong. Our approach hinges on a key bound for bisections of graphs with sparse neighborhoods concerning the degree sequence. The result is inspired by the celebrated approximation algorithm of Goemans and Williamson and appears to be worthy of future exploration.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。