On MaxCut and the Lovász theta function

In this short note we prove a lower bound for the MaxCut of a graph in terms of the Lovász theta function of its complement. We combine this with known bounds on the Lovász theta function of complements of \(H\)-free graphs to recover many known results on the MaxCut of \(H\)-free graphs. In particu...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-09
Main Authors: Balla, Igor, Janzer, Oliver, Sudakov, Benny
Format: Article
Language:English
Subjects:
Graphs
Lower bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this short note we prove a lower bound for the MaxCut of a graph in terms of the Lovász theta function of its complement. We combine this with known bounds on the Lovász 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\).
ISSN:2331-8422