Max-Bisections of graphs without even cycles

Jianfeng Hou, Siwei Lin, Qinghou Zeng

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 biparti…