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

About 2 years old · traced to

Fix k≥2k\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 C2k−1C_{2k-1}-free graph GG on nn vertices satisfying

(1/4−δ0)n2≥e(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 G∗G^* 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.

References

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.