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

About 7 years old · traced to

Let r≥2r\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 G⊗HG\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 Kr−2⊗C5K_{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 Kr−2⊗C5K_{r-2}\otimes C_5 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

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.