New for: D1, D2, D3, D4, D5
Surprisingly, the best known bound is only O(n log(n)), whereas for n^{\eps} \le k \le n^{1-\eps} colors, \Theta(n) guesses are necessary and sufficient.
In this talk, I'll give a good argument why such a gap is natural, and a better one, why not.
This is on-going work with Reto Spoehel, Henning Thomas (ETH) and Carola Winzen.