Balanced max-part conjecture for K_4-free graphs
Balanced max-part conjecture for K_4-free graphs
Let be even and let be a -free graph on vertices. A balanced -partition is a partition with . Balanced max-part conjecture for K_4-free graphs. There exists a balanced -partition such that each class spans at most edges:
The bound is sharp for the complete 3-partite graph with class sizes , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.