[siegelzero]

I can recommend the book Guide to Graph Colouring: Algorithms and Applications by Lewis. It covers techniques including some state of the art methods for getting good but not provably optimal colorings. It discusses in depth local search and hybrid evolutionary algorithms, which tend to be the best performing on academic benchmarks (DIMACS graphs and large random graphs).