New results for MaxCut in H$H$‐free graphs

DOI10.1112/jlms.12750zbMath1519.05133arXiv2104.06971MaRDI QIDQ6134889

Stefan Glock, Oliver Janzer, Benjamin Sudakov

Publication date: 23 August 2023

Published in: Journal of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

MaxCut problempseudo-random \(C_r\)-free graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Related Items

MAX-CUT BY EXCLUDING BIPARTITE SUBGRAPHS, Making an H $H$‐free graph k $k$‐colorable, Graph partitioning: an updated survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Eigenvalues and forbidden subgraphs. I.
• Laplacian eigenvalues and the maximum cut problem
• Explicit Ramsey graphs and orthonormal labelings
• Approximating the independence number via the \(\vartheta\)-function
• Maximum cuts and judicious partitions in graphs without short cycles
• Hypergraph cuts above the average
• The smallest eigenvalue of \(K_{r}\)-free graphs
• 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 of graphs with forbidden cycles
• Lower Bounds for Max-Cut in $H$-Free Graphs via Semidefinite Programming
• A generalization of Turán's theorem
• Some Extremal Properties of Bipartite Subgraphs
• MaxCut in ${\bm H)$-Free Graphs
• Making an H $H$‐free graph k $k$‐colorable