Cycle-count conjecture for degree 3-critical graphs
Cycle-count conjecture for degree 3-critical graphs
A degree 3-critical graph is a graph on vertices with edges and no proper induced subgraph of minimum degree . Cycle-count conjecture. Every degree -critical graph on vertices contains cycles of at least
distinct lengths. The conjecture is motivated by the Bollobás–Brightwell construction, which gives degree -critical graphs with no cycles longer than . 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
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.