On the size of maximum cut in planar graphs

2023/01/22 by Pranay Gorantla, Gorantla, Pranay, Santhoshini Velusamy +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2301.09170

openalex publication_date 2023/01/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the size of maximum cut in a planar graph with m edges is at least 2m/3. We also show that maximal planar graphs saturate this bound.

Related

• Lower bounds for Max-Cut in H-free graphs via semidefinite programming
• Parameterized Algorithms for Maximum Cut with Connectivity Constraints
• On the maximum number of edges in planar graphs of bounded degree and matching number
• Fixed-Parameter Algorithms for the Weighted Max-Cut Problem on Embedded\n 1-Planar Graphs
• Exact Algorithms for the Maximum Planar Subgraph Problem: New Models and Experiments