Erdős–Faudree–Rousseau conjecture on edges occurring in odd cycles

Let GG be an nn-vertex graph with

|E(G)|=\left\left\oldlfloor\frac{n^2}{4}\right\right\oldrfloor+1.

Let C2k+1C_{2k+1} denote the cycle of length 2k+12k+1, and say that an edge occurs in C2k+1C_{2k+1} if it belongs to a copy of that cycle. Fix an integer k2k\ge 2. Erdős–Faudree–Rousseau conjecture. Every such graph contains at least

29n2O(n)\frac{2}{9}n^2-O(n)

edges that occur in C2k+1C_{2k+1}. This conjecture asserts that the construction consisting of a complete graph and a complete balanced bipartite graph as two 22-connected blocks overlapping in one vertex is extremal up to the linear error term. The case k=2k=2 was identified as an open problem in the cited work; no resolution is supplied here.

Sources & referencesView supporting material

Primary source

Andrzej Grzesik, Ping Hu and Jan Volec, “Minimum number of edges that occur in odd cycles”, arXiv:1605.09055 (2018).

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.