The C3+1C_{3\ell+1}-free clique extremal conjecture

From papers

Let k2k\geq 2 and let nn be sufficiently large. Let GG be an nn-vertex graph containing no cycle C3+1C_{3\ell+1} for any integer k\ell\geq k. For r2r\geq 2, write Nr(G)N_r(G) for the number of cliques of size rr in GG. Clique extremal conjecture.

Nr(G)n13k1(3kr).N_r(G)\leq \frac{n-1}{3k-1}\binom{3k}{r}.

Equality holds if and only if n1n-1 is divisible by 3k13k-1 and GG is a connected nn-vertex graph consisting of n13k1\frac{n-1}{3k-1} maximal 22-connected blocks, each isomorphic to K3kK_{3k}. This conjecture asks whether the sharp block-decomposition phenomenon proved in the paper for sufficiently restricted odd circumferences extends to the family of forbidden cycle lengths congruent to 11 modulo 33; its resolution is not supplied here.

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

Zequn Lv, Ervin Győri, Zhen He, Nika Salia, Chuanqi Xiao and Xiutao Zhu, “The maximum number of cliques in graphs with bounded odd circumference”, arXiv:2212.01989 (2022).

Solutions 0

No solutions have been posted yet.