Cycle-count conjecture for degree 3-critical graphs

A degree 3-critical graph is a graph on nn vertices with 2n22n-2 edges and no proper induced subgraph of minimum degree 33. Cycle-count conjecture. Every degree 33-critical graph on nn vertices contains cycles of at least

3log2n+O(1)3\log_2 n+O(1)

distinct lengths. The conjecture is motivated by the Bollobás–Brightwell construction, which gives degree 33-critical graphs with no cycles longer than 4log2n+O(1)4\log_2 n+O(1). Determining the minimum possible number of distinct cycle lengths remains open.

Sources & referencesView supporting material

Primary source

Lothar Narins, Alexey Pokrovskiy and Tibor Szabó, “Graphs without proper subgraphs of minimum degree 3 and short cycles”, arXiv:1408.5289 (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.