Korándi–Roberts–Scott conjecture on blowups of odd-cycle-free graphs

Fix k2k\ge 2. Let δ>δ0>0\delta>\delta_0>0 and let nn be sufficiently large. For a graph GG, write D2(G)D_2(G) for the maximum number of edges in a bipartite subgraph of GG, and call a graph obtained by replacing vertices of a graph with independent sets according to its adjacency pattern a blowup. Korándi–Roberts–Scott conjecture. For every C2k1C_{2k-1}-free graph GG on nn vertices satisfying

(1/4δ0)n2e(G)(1/4δ)n2,(1/4-\delta_0)n^2\ge e(G)\ge(1/4-\delta)n^2,

there is a C2k+1C_{2k+1}-blowup GG^* such that

e(G)e(G)andD2(G)D2(G).e(G^*)\ge e(G)\quad\text{and}\quad D_2(G^*)\ge D_2(G).

This conjecture concerns the structure of graphs with edge density close to one quarter and is presented as a way to extend the range of near-extremal results for odd-cycle-free graphs. No resolution is given in the supplied text.

Sources & referencesView supporting material

Primary source

Zilong Yan and Yuejian Peng, “A strong structural stability of C_2k+1-free graphs”, arXiv:2408.15487 (2024).

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.