Structural conjecture for near-extremal Kr+1K_{r+1}-free graphs

From papers

Let r2r\geq 2 be an integer, let nn be sufficiently large, and let Dr(G)D_r(G) denote the minimum number of edges that must be deleted from a graph GG to make it rr-partite. For graphs GG and HH, write GHG\otimes H 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 α0>0\alpha_0>0 such that, for every 0αα00\leq\alpha\leq\alpha_0 and every Kr+1K_{r+1}-free graph GG on nn vertices, there is an unbalanced blow-up HH of Kr2C5K_{r-2}\otimes C_5 on nn vertices satisfying

e(H)e(G)e(H)\geq e(G)

and

Dr(G)Dr(H).D_r(G)\leq D_r(H).

The conjecture proposes that the worst examples for the distance from rr-partiteness among near-extremal Kr+1K_{r+1}-free graphs have the form of unbalanced Kr2C5K_{r-2}\otimes C_5 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

No solutions have been posted yet.