The bipartite Turán graph conjecture for cycle-maximal triangle-free graphs

Let a cycle-maximal triangle-free graph be a triangle-free graph to which no edge can be added without creating a triangle. For a graph on nn vertices, let Kn/2,n/2K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil} denote the balanced complete bipartite graph. The bipartite Turán graph conjecture. The cycle-maximal triangle-free graphs are exactly the bipartite Turán graphs

Kn/2,n/2K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}

for all nn. The conjecture was verified by exhaustive computer search for n13n\leq 13; it proposes that balanced complete bipartite graphs maximize the number of cycles among cycle-maximal triangle-free graphs.

Sources & referencesView supporting material

Primary source

Stephane Durocher, David S. Gunderson, Pak Ching Li and Matthew Skala, “Cycle-maximal triangle-free graphs”, arXiv:1310.5172 (2014).

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.