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

About 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

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.