Probably no theoretical algorithm "faster than brute-force" will be as good as using a SAT solver in practice. If you know the chromatic number already, it suffices to solve a single instance of SAT to find the coloring. Moreover, since you know the instance is always satisfiable, you can also try local search solvers such as Sparrow.
The SAT encoding of k-colorability of straightforward. In my experience the obvious encoding works fine for many instances. Of course, there are multiple ways of encoding the problem some of which can work better for certain instances, but it's hard to know without trying them out. A good symmetry breaking technique which will also speed up things nicely is to find a clique (as large as possible - for sparse graphs there are extremely good practical solvers like pmc), forcing it to have distinct colors, and then feeding that instance to the SAT solver.
I helped implement this very approach to the IGraphM Mathematica library and it works quite nicely.