Ore's periodicity conjecture for the minimum size of k-critical graphs

Let fk(n)f_k(n) denote the minimum number of edges in a kk-critical graph on nn vertices, where a graph is kk-critical if its chromatic number is kk and every proper subgraph is (k1)(k-1)-colorable.

Ore's conjecture. If k4k\geq4, then

fk(n+k1)=fk(n)+(k1)(k21k1).f_k(n+k-1)=f_k(n)+(k-1)\left(\frac{k}{2}-\frac{1}{k-1}\right).

This conjecture predicts the exact periodic behavior of the minimum edge count of kk-critical graphs. The paper's abstract says that Kostochka and Yancey proved an asymptotic form of Ore's conjecture, while the exact assertion is not identified there as resolved.

Sources & referencesView supporting material

Primary source

Ron Gould, Victor Larsen and Luke Postle, “Structure in sparse k-critical graphs”, arXiv:2107.00976 (2021).

Additional references

2 papers in this index state this conjecture (2012–2021). The statement above is taken from the most recent of them; the others are arXiv:1209.1050.

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.