Maximum bisections of graphs without cycles of length 4 (Q2142653)

A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differs by at most 1, and its size is the number of edges that go across the two parts. Let \(\theta (\ell_1, \ell_2, \ell_3)\) denote the graph consisting of three internally disjoint paths of length \(\ell_1\), \(\ell_2\) and \(\ell_3\), respectively, each with the same endpoints. The authors prove new lower bounds for the maximum size of a bisection of \(\{C_4\} \cup \Theta_6\)-free graphs, where \(\Theta_6 = \{\theta(1,2,4), \theta(2,3,3), \theta(3,3,3)\}\) and \(C_4\) denotes the circuit of length \(4\).