Structural conjecture for near-extremal -free graphs
Let be an integer, let be sufficiently large, and let denote the minimum number of edges that must be deleted from a graph to make it -partite. For graphs and , write for their join, and let an unbalanced blow-up mean a blow-up whose vertex classes need not have equal sizes.
Structural conjecture. There exists such that, for every and every -free graph on vertices, there is an unbalanced blow-up of on vertices satisfying
and
The conjecture proposes that the worst examples for the distance from -partiteness among near-extremal -free graphs have the form of unbalanced blow-ups. The supplied text does not state whether this structural statement has been resolved.
References
Primary source
József Balogh, Felix Christian Clemen, Mikhail Lavrov, Bernard Lidický and Florian Pfender, “Making K_r+1-Free Graphs r-partite”, arXiv:1910.00028 (2019).
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
No solutions have been posted yet.