Narins–Pokrovskiy–Szabó conjecture on cycle-length diversity in degree 3-critical graphs
Narins–Pokrovskiy–Szabó conjecture on cycle-length diversity in degree 3-critical graphs
A graph is degree 3-critical if it has vertices, edges, and no proper induced subgraph with minimum degree at least . Narins–Pokrovskiy–Szabó conjecture. Every degree 3-critical graph on vertices contains cycles of at least
distinct lengths. The source proves a lower bound of , 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
Sign in to submit a solution.
No solutions have been posted yet.