Graph colouring is NP-Complete, and many real world problems map fairly naturally to it. I wrote a program that factors integers by colouring graphs as a demon

Graph colouring is NP-Complete, and many real world problems map fairly naturally to it. I wrote a program that factors integers by colouring graphs as a demonstrator, but it's easy enough to use colouring to solve SAT problems. In compiler technology, "register colouring" is a thing, although no longer necessarily the best technique to solve the particular problem. Optimal Route Computation can be cast as a graph colouring problem, as can scheduling. I recorded a talk about this some time ago in which I proved that G3C (Graph 3-Colouring) is NPC, let me know if you'd like a link and I'll see if it's still available. If not, I'm giving it again as a part of the G4G Celebration of Mind series of talks.