Dense halves in balanced 2-partition of K4-free graphs

2024/12/18 by Yue Xu, Xiaodong Zhang, Xu, Yue +1
Computer Science · Mathematics · #05C35 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2412.13485

openalex publication_date 2024/12/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A balanced 2-partition of a graph is a bipartition A,A^c of V(G) such that |A|=|A^c|. Balogh, Clemen, and Lidický conjectured that for every K₄-free graph on n (even) vertices, there exists a balanced 2-partition A,A^c such that max\e(A),e(A^c)\≤ n²/16 edges. In this paper, we present a family of counterexamples to the conjecture and provide a new upper bound (0.074n²) for every sufficiently large even integer n.

Related

• 10 Problems for Partitions of Triangle-free Graphs
• Partitions of Graphs into Special Bipartite Graphs
• Sparse halves in K₄-free graphs
• Balanced subdivisions of cliques in graphs
• On the extremal number of subdivisions