Narins–Pokrovskiy–Szabó conjecture on cycle-length diversity in degree 3-critical graphs

From papers

A graph is degree 3-critical if it has nn vertices, 2n22n-2 edges, and no proper induced subgraph with minimum degree at least 33. Narins–Pokrovskiy–Szabó conjecture. Every degree 3-critical graph on nn vertices contains cycles of at least

3logn+O(1)3\log n+O(1)

distinct lengths. The source proves a lower bound of logn3+log3+O(1)\frac{\log n}{3+\log 3}+O(1), so the conjecture remains open up to a constant factor.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Francesco Di Braccio, Kyriakos Katsamaktsis, Jie Ma, Alexandru Malekshahian and Ziyuan Zhao, “Leaf-to-leaf paths and cycles in degree-critical graphs”, arXiv:2504.11656 (2026).

Solutions 0

No solutions have been posted yet.