Lower Bounds for Maximum Weighted Cut

DOI10.1137/21M1411913MaRDI QIDQ6100613zbMATH OpenOpenAlexFDO

Authors G. Gutin, A. Yeo

Publication date 22 June 2023

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

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

zbMATH Keywords

weighted graphbipartite subgraphweighted max cut

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: While there have been many results on lower bounds for Max Cut in unweighted graphs, the only lower bound for non-integer weights is that by Poljak and Turz{'{i}}k (1986). In this paper, we launch an extensive study of lower bounds for Max Cut in weighted graphs. We introduce a new approach for obtaining lower bounds for Weighted Max Cut. Using it, Probabilistic Method, Vizing's chromatic index theorem, and other tools, we obtain several lower bounds for arbitrary weighted graphs, weighted graphs of bounded girth and triangle-free weighted graphs. We pose conjectures and open questions.

Recommendations

• scientific article; zbMATH DE number 1787231
• Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
• Lower bounds for max-cut in \(H\)-free graphs via semidefinite programming
• A class of spectral bounds for max \(k\)-cut
• New lower bounds on the weighted chromatic number of a graph

Cites work

• scientific article; zbMATH DE number 3869331 (Why is no real title available?)
• scientific article; zbMATH DE number 1787231 (Why is no real title available?)
• A note on bipartite subgraphs of triangle‐free graphs
• A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
• Bipartite subgraphs
• Bipartite subgraphs of integer weighted graphs
• Extremal bipartite subgraphs of cubic triangle-free graphs
• Hamilton Paths in Grid Graphs
• Introduction to algorithms.
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• Lower bounds for max-cut via semidefinite programming
• MaxCut in ${\bm H)$-Free Graphs
• Node-and edge-deletion NP-complete problems
• On the maximum number of five-cycles in a triangle-free graph
• On the number of pentagons in triangle-free graphs
• Reducibility among combinatorial problems
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(3)

• Edge-Cuts of Optimal Average Weights
• Bounds on maximum weight directed cut
• Sharpened lower bounds for cut elimination

This page was built for publication: Lower Bounds for Maximum Weighted Cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6100613)