alt Hacker NewsNot much faster. Any k-coloring algorithm of complexity F(n) can be used to create a chromatic number algorithm of complexity lg(N)F(N) simply by bisecting on N.
Not much faster. Any k-coloring algorithm of complexity F(n) can be used to create a chromatic number algorithm of complexity lg(N)F(N) simply by bisecting on N.
A small tip: if you want to do this trick, with an exponential F, you probably want a linear search rather than a binary search.
If your k << N then F(N/2) is going to eat up all of the running time of ΣF(i).