Many problems can be reduced to graph coloring problems if you look at it the right way. Try understanding the standard examples (see the applications section in Wikipedia), then it is really easy to come up with your own applications.