Hello everyone.

Recently I encountered a problem which included checking whether given graph is colorable using k colours. More specifically:

• graphs given are quite large (up to several thousands of vertices) but not very dense (average degree is about 10-20, max degree may be about 50).

• k is not too big (something up to 10).

• it is important to get a reliable answer (even one-sided error is not tolerated).

I stumbled upon a lib that is able to count the chromatic number of a graph (notable that it does quite well on average for that scale, still some instances take very long to treat). k-colorability checking sure is simpler than counting the chromatic number, so specialized solution for it is expected to do somewhat better; sadly I couldn't find any code or description of practical solution for this problem.

Do you have any experience with this particular problem or something related? What did you use and what results have you got? Any advice, useful links and relevant comments are also encouraged. Thanks.