2017/09/28 by GENGHUA FAN, Genghua Fan, Jianfeng Hou +3
Computer Science · Mathematics · #Interconnection Networks and Systems #Advanced Graph Theory Research #Graph theory and applications
paper · doi:10.1017/s0963548317000487
Bollobás and Scott ( Random Struct. Alg. 21 (2002) 414–430) asked for conditions that guarantee a bisection of a graph with m edges in which each class has at most (1/4+ o (1)) m edges. We demonstrate that cycles of length 4 play an important role for this question. Let G be a graph with m edges, minimum degree δ, and containing no cycle of length 4. We show that if (i) G is 2-connected, or (ii) δ ⩾ 3, or (iii) δ ⩾ 2 and the girth of G is at least 5, then G admits a bisection in which each class has at most (1/4+ o (1)) m edges. 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 many m there exists a graph with m edges and girth at least 5 for which any bisection has at least (1/4− o (1)) m edges in one of the two classes.