Igor Balla, Oliver Janzer, Benny Sudakov
Published 2023-05-29Version 1
In this short note we prove a lower bound for the MaxCut of a graph in terms of the Lov\'asz theta function of its complement. We combine this with known bounds on the Lov\'asz theta function of complements of $H$-free graphs to recover many known results on the MaxCut of $H$-free graphs. In particular, we give a new, very short proof of a conjecture of Alon, Krivelevich and Sudakov about the MaxCut of graphs with no cycles of length $r$.
Some Results on $k$-Critical $P_5$-Free Graphs
Turán numbers for $K_{s,t}$-free graphs: topological obstructions and algebraic constructions
Vertex-Critical $(P_5, chair)$-Free Graphs
![QR code for arXiv:2305.18252 [math.CO]](http://oss.arxitics.com/images/favicon.svg)