Maximum bisections of graphs with girth at least six (Q6640955)

Given a graph \(G\), the Max Cut problem asks to find a bipartition \((V_1,V_2)\) of \(V(G)\) which maximizes the size of the cut \(e(V_1, V_2)\), namely the number of edges across the two parts. Erdős and Lovász initiated the study of Max Cut for \(C_3\)-free graphs, where \(C_k\) denotes the cycle of length \(k\). A balanced bipartition also known as a bisection is a bipartition such that the number of vertices in the two parts differ by at most one. The Max Bisection problem is finding a graph bisection that maximizes its size. \textit{M. Rao} et al. [Discrete Math. 345, No. 8, Article ID 112914, 11 p. (2022; Zbl 1495.05266)] conjectured that a \(C_4\) free graph \(G\) with \(n=|V(G)|\) and \(m=|E(G)|\) along with perfect matchings and degree sequence \(d_1, d_2, \ldots, d_n\) admit a bisection of size at least \((m/2)+\Omega((d_1)^{(1/2)} +\dots + (d_n)^{(1/2)})\). The authors of this paper nicely prove that it is so if the girth of \(G\) is at least 6 and \(G\) has a perfect matching, partly confirming the conjecture.