Bisections of Graphs Without Short Cycles
Genghua Fan, Jianfeng Hou, Xingxing Yu · Combinatorics Probability Computing · 2017
Bollobás and Scott (Random Struct. Alg.21(2002) 414–430) asked for conditions that guarantee a bisection of a graph withmedges in which each class has at most (1/4+o(1))medges. We demonstrate that cycles of length 4 play an important role for this question. LetGbe a graph withmedges, minimum degree δ, and containing no cycle of length 4. We show that if (i)Gis 2-connected, or (ii) δ ⩾ 3, or (iii) δ ⩾ 2 and the girth ofGis at least 5, thenGadmits a bisection in which each class has at most (1/4+o(1))medges. We show that each of these conditions are best possible. On the other hand, a construction by Alon, Bollobás, Krivelevich and Sudakov shows that for infinitely manymthere exists a graph withmedges and girth at least 5 for which any bisection has at least (1/4−o(1))medges in one of the two classes.