Conjecture on extremal graphs for linearly long induced cycles

From papers

Let c(0,1)c\in(0,1), let l(n)=cnl(n)=\lceil cn\rceil, and let c(n,l)c(n,l) be the maximum number of induced cycles of length ll in a graph on nn vertices. Let C(n,l)C(n,l) be the set of graphs attaining this maximum, and call a graph a cyclic braid of length ll as in the paper. The linear-length induced-cycle conjecture. If l(n)=cnl(n)=\lceil cn\rceil, then for sufficiently large nn the only graphs in C(n,l)C(n,l) are cyclic braids of length ll. The paper determines the extremal graphs for several related induced-cycle problems, but this linear-length question is presented as an expected statement and remains unresolved.

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

Natasha Morrison and Alex Scott, “Maximising the number of induced cycles in a graph”, arXiv:1603.02960 (2017).

Solutions 0

No solutions have been posted yet.