Balogh–Clemen–Lidický conjecture on the balanced bipartite distance of K4K_4-free graphs

From papers

Let GG be a K4K_4-free graph on nn vertices. The Balogh–Clemen–Lidický conjecture. GG can be made balanced bipartite by removing at most

n29\frac{n^2}{9}

edges. This conjecture asks whether the sharp bipartite-distance bound for K4K_4-free graphs matches the bound suggested by the complete tripartite graph. The surrounding text identifies it as a conjecture of Balogh, Clemen, and Lidický; no resolution is given here.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

József Balogh, Ignacy Buczek, Andrzej Grzesik and Piotr Kuc, “Balanced bipartite distance of K_4-free graphs”, arXiv:2605.05346 (2026).

Additional references

2 papers in this index state this conjecture (2024–2026). The statement above is taken from the most recent of them; the others are arXiv:2412.13485.

Solutions 0

No solutions have been posted yet.