Lower Bounds for Maximum Weighted Cut

DOI10.1137/21M1411913zbMATH Open1517.05140arXiv2104.05536OpenAlexW4380886424MaRDI QIDQ6100613FDOQ6100613

A. Yeo, G. Gutin

Publication date: 22 June 2023

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

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.

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)

Cites Work

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

Cited In (3)

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

   Recommendations

• Title not available (Why is that?) 👍 👎
• 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 👍 👎

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)