Paperlane

no. 10 · Friday 6 November 2026

Seeking the dense half in $K_4$-free graphs

Ignacy Buczek, Andrzej Grzesik and Piotr Kuc

math.CO

Abstract

We show that every $K_4$-free graph on $n$ vertices has a balanced bipartition such that neither part contains more than $0.0671n^2 + o(n^2)$ edges. This improves the previous best bound of $0.074n^2$ by Xu and Zhang. We also formulate a conjecture that the tight bound for this problem is $\frac{425}{6498}n^2 \approx 0.0654n^2$, and present a construction showing that it would be best possible.

fields
Combinatorics
pdf ↗ page arXiv:2611.07082 ↗