← All problems

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

14 years old · traced to

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 (k−1)(k-1)-colorable.

Ore's conjecture. If k≥4k\geq4, then

fk(n+k−1)=fk(n)+(k−1)(k2−1k−1).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.

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.

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

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.