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.