The bipartite Turán graph conjecture for cycle-maximal triangle-free graphs
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 vertices, let 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
for all . The conjecture was verified by exhaustive computer search for ; 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.