Conjecture on cycles in odd-cycle-free graphs

Let k>1k>1, and let C2k+1C_{2k+1} denote the cycle of length 2k+12k+1. A graph is C2k+1C_{2k+1}-free if it contains no subgraph isomorphic to C2k+1C_{2k+1}; Ka,bK_{a,b} denotes the complete bipartite graph with parts of sizes aa and bb. Odd-cycle-free cycle conjecture. For any k>1k>1, if an nn-vertex C2k+1C_{2k+1}-free graph GG has the maximum number of cycles, then

G=Kn2,n2.G=K_{\left \lceil \frac{n}{2}\right \rceil,\left \lfloor \frac{n}{2}\right \rfloor}.

The conjecture extends the extremal cycle question from triangle-free graphs to longer odd-cycle exclusions. The surrounding discussion notes related extremal edge and maximal-graph results, but the conjecture's resolution is not supplied.

Sources & referencesView supporting material

Primary source

Andrii Arman, David S. Gunderson and Sergei Tsaturian, “Triangle-free graphs with the maximum number of cycles”, arXiv:1501.01088 (2015).

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.