[datadrivenangel]

"More precisely, it is NP-hard1. So it is unlikely that we will find an efficient algorithm to optimally solve the coloring problem on an arbitrary input graph. This fundamental hardness result casts a long shadow across the landscape of graph coloring."

[HarHarVeryFunny]

Yes, but in practice heuristic approaches can work well, even if there are no guarantees of optimality. See for example my response about a simple "most constrained first" heuristic.