{"id":"arxiv/2611.07082","url":"https://arxiv.org/abs/2611.07082","tags":["math.CO"],"score":0,"title":"Seeking the dense half in $K_4$-free graphs","domain":"math.CO","source":"arxiv","authors":["Ignacy Buczek","Andrzej Grzesik","Piotr Kuc"],"reviews":0,"subject":"math.CO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-04","reactions":{}}