Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality (Q1297468)

The paper studies local switching algorithms to find large cuts satisfying several constraints in a simple undirected graph \(G= (V,E)\). In particular, two new lower bounds are given for the max cut, \(b(G)\). If \(G\) is connected and has odd girth at least \(2t\) \((t\geq 1)\), then \(b(G)\geq {| E|\over 2}+ {2t- 1\over 4t} (| V|- 1)\). This inequality is tight. Another new lower bound for the max cut is \(b(G)\geq {| E|\over 2}+{1\over 4} (| V|+ \text{odd}(G)- c(G))\), where \(\text{odd}(G)\) is the maximum number of odd-degree edge-disjoint stars in \(G\), and \(c(G)\) is the number of connected components of \(G\). This new lower bound improves on the Edwards-Erdős lower bound \(b(G)\geq {| E|\over 2}+{1\over 4} (| V|- 1)\), whenever \(G\) has vertices of odd degree.