Many of these issues (and potential solutions) are discussed in my 2021 book

Lewis, R. (2021) A Guide to Graph Colouring: Algorithms and Applications (second ed.). Springer. ISBN: 978-3-030-81053-5.

This is accompanied by a suite of C++ algorithms. I have also written a Python library for graph colouring that includes heuristics for handling very large graphs.