Structural conjecture for near-extremal -free graphs
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
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).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.