Balanced max-part conjecture for K_4-free graphs

Let nn be even and let GG be a K4K_4-free graph on nn vertices. A balanced 22-partition is a partition V(G)=ABV(G)=A\cup B with A=B=n/2|A|=|B|=n/2. Balanced max-part conjecture for K_4-free graphs. There exists a balanced 22-partition such that each class spans at most n2/16n^2/16 edges:

max{e(A),e(B)}n2/16.\max\{e(A),e(B)\}\leq n^2/16.

The bound is sharp for the complete 3-partite graph with class sizes n/2,n/4,n/4n/2,n/4,n/4, and the conjecture is proved in the source for 3-partite graphs but remains open in general.

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.