On MaxCut and the Lov\'asz theta function
2023
Online
report
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$.
Comment: 8 pages
Titel: |
On MaxCut and the Lov\'asz theta function
|
---|---|
Autor/in / Beteiligte Person: | Balla, Igor ; Janzer, Oliver ; Sudakov, Benny |
Link: | |
Veröffentlichung: | 2023 |
Medientyp: | report |
Schlagwort: |
|
Sonstiges: |
|