Sudakov's bipartisation conjecture for K_{r+1}-free graphs

For a graph GG, let D2(G)D_2(G) be the minimum number of edges that must be deleted to make GG bipartite. Fix r3r\geq3, and let GG be an nn-vertex Kr+1K_{r+1}-free graph. Sudakov's bipartisation conjecture.

D2(G){(r1)24r2n2,r odd,r24rn2,r even.D_2(G)\leq\begin{cases}\frac{(r-1)^2}{4r^2}n^2,& r\text{ odd},\frac{r-2}{4r}n^2,& r\text{ even}.\end{cases}

The conjecture is known for r=5r=5 by flag algebras, whereas the even-rr cases are described as more difficult and remain open.

Sources & referencesView supporting material

Primary source

József Balogh, Felix Christian Clemen and Bernard Lidický, “10 Problems for Partitions of Triangle-free Graphs”, arXiv:2203.15764 (2022).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.