Lower Bounds for Max-Cut in $H$-Free Graphs via Semidefinite Programming

DOI10.1137/20M1333985zbMath1475.05094arXiv1810.10044OpenAlexW3178878483MaRDI QIDQ5001844

Luca Trevisan, Charles Carlson, Alexandra Kolla, Nitya Mani, Ray Li, Benjamin Sudakov

Publication date: 23 July 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.10044

zbMATH Keywords

semidefinite programmingextremal combinatorics\(H\)-free graphsmax cut

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Semidefinite programming (90C22)

Related Items (3)

MAX-CUT BY EXCLUDING BIPARTITE SUBGRAPHS ⋮ Graph partitioning: an updated survey ⋮ New results for MaxCut in H$H$‐free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How to make a graph bipartite
• Making a \(K_4\)-free graph bipartite
• Bipartite subgraphs of integer weighted graphs
• Maximum cuts and judicious partitions in graphs without short cycles
• Hypergraph cuts above the average
• Bipartite subgraphs
• A note on bipartite subgraphs of triangle‐free graphs
• Bipartite Subgraphs of Triangle-Free Graphs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• MAXIMUM CUTS IN GRAPHS WITHOUT WHEELS
• BIPARTITE SUBGRAPHS OF -FREE GRAPHS
• Some Extremal Properties of Bipartite Subgraphs
• MaxCut in ${\bm H)$-Free Graphs

This page was built for publication: Lower Bounds for Max-Cut in $H$-Free Graphs via Semidefinite Programming