Balanced 3-partition conjecture for K_4-free graphs

Let nn be divisible by 33 and let GG be a K4K_4-free graph on nn vertices. A balanced 33-partition divides V(G)V(G) into three classes of size n/3n/3; class-edges are edges whose endpoints lie in the same class. Balanced 3-partition conjecture for K_4-free graphs. There exists a balanced 33-partition with at most

481n2\frac{4}{81}n^2

class-edges. This is one of the paper's open partition problems for K4K_4-free graphs, and no general resolution is supplied.

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.