Tight bounds for judicious 3-partitions of graphs

2025/09/25 by Kuang, Peiru, Wang, Yan
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2509.20994

Abstract

In this paper, we show that every graph with m edges admits a 3-partition such that max_{1 ≤ i ≤ 3} e(V_i) ≤ (m)/(9) + (1)/(9)h(m) and e(V₁, V₂, V₃) ≥ (2)/(3)m + (1)/(3)h(m), where h(m) = √(2m + 1/4) - 1/2. This answers a problem of Bollobás and Scott affirmatively. We also solve several related problems of Bollobás and Scott. All of our results are tight.

Citations

• Judicious Partitions in Edge-Weighted Graphs with Bounded Maximum Weighted Degree
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Some Extremal Properties of Bipartite Subgraphs

Related

• Judiciously 3-partitioning 3-uniform hypergraphs
• Judiciously 3‐partitioning 3‐uniform hypergraphs
• Problems and results on judicious partitions
• Judicious Partitions in Edge-Weighted Graphs with Bounded Maximum Weighted Degree
• A local search 4/3-approximation algorithm for the minimum 3-path partition problem