On MaxCut and the Lov\'asz theta function

DOI10.1090/PROC/16675MaRDI QIDQ6438366zbMATH OpenOpenAlexFDO

Authors Igor Balla, Oliver Janzer, Benny Sudakov

Publication date 29 May 2023

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)

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

Recommendations

• Lower bounds for max-cut in \(H\)-free graphs via semidefinite programming
• MaxCut in ${\bm H)$-Free Graphs
• New results for MaxCut in H$H$‐free graphs
• Maximum cuts in \(\mathscr{H} \)-free graphs
• Lower bounds for max-cut via semidefinite programming

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)