Voss's conjecture on chords in odd cycles of critical graphs

All graphs are finite and simple. A graph is kk-critical if its chromatic number is kk and every proper subgraph is (k1)(k-1)-colorable. Let gk(n)g_k(n) be the largest integer α\alpha such that every nn-vertex kk-critical graph, with k4k\geq4, contains an odd cycle with at least α\alpha chords. Voss's conjecture.

limngk(n)=.\lim_{n\to\infty}g_k(n)=\infty.

This asks whether criticality forces increasingly chord-rich odd cycles as the order grows. The paper states that its results disprove the conjecture for every fixed k4k\geq4, so it is refuted.

Sources & referencesView supporting material

Primary source

Xiaozheng Chen and Bo Ning, “Cycle lengths and chords under chromatic and degree constraints”, arXiv:2607.15501 (2026).

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.