Linear chords in minimum-degree-3 cycles

Status partial high confidence

Question 4.3 asks whether every graph with minimum degree 3 contains a cycle of length ℓ with at least cℓ chords for some constant c>0. Draganć and Girão (arXiv:2601.08769, 2026) proved that constant minimum degree suffices to guarantee a cycle of length ℓ with Ω(ℓ/log^C ℓ) chords, citing arXiv:2502.04726 directly. This achieves almost-linear chord count under constant minimum degree, but falls short of the conjectured exactly linear bound cℓ; the full statement of Question 4.3 remains open.

Cited literature (1)

• partial Cycles with almost linearly many chords (2026)
  Nemanja Draganć, António Girão · arXiv preprint · arXiv:2601.08769

  Proves that every graph with sufficiently large constant minimum degree δ(G) ≥ C contains a cycle of length ℓ with Ω(ℓ/log^C ℓ) chords, achieving almost-linear chord count and citing arXiv:2502.04726 explicitly, but stopping short of the linear bound cℓ asked in Question 4.3.

Reviewer notes. The follow-up paper arXiv:2601.08769 directly cites the source paper and proves a related but weaker result: almost-linear (Ω(ℓ/log^C ℓ)) rather than linear (Ω(ℓ)) chord count. Whether minimum degree 3 specifically suffices (as opposed to a larger constant), and whether the chord count can be made exactly linear, both remain open.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).