Balanced bipartite distance of $K_4$-free graphs

József Balogh; Ignacy Buczek; Andrzej Grzesik; Piotr Kuc

Balanced bipartite distance of $K_4$-free graphs

József Balogh, Ignacy Buczek, Andrzej Grzesik, Piotr Kuc

arXivarxiv/2605.05346May 6, 2026math.COscore 0

We show that every $K_4$-free graph on $n$ vertices can be made balanced bipartite by removing at most $\frac{n^2}{9}$ edges. This proves a conjecture of Balogh, Clemen, and Lidický, and generalizes both Sudakov's result on the bipartite distance of $K_4$-free graphs and Reiher's result on the sparse half of $K_4$-free graphs.

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.05346
curl -X POST /api/v1/records/arxiv/2605.05346/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.05346/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'