On MaxCut and the Lov\'asz theta function

DOI10.1090/PROC/16675arXiv2305.18252OpenAlexW4387343333MaRDI QIDQ6438366FDOQ6438366

Authors: Igor Balla, Oliver Janzer, Benny Sudakov 

Publication date: 29 May 2023

Abstract: 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$.

Full work available at URL: https://doi.org/10.1090/proc/16675

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35)

Cited In (1)

• Orthonormal representations, vector chromatic number, and extension complexity

This page was built for publication: On MaxCut and the Lov\'asz theta function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6438366)