Brelaz's Heuristic Algorithm can be used to find a good, but not necessarily minimal, Vertex coloring of a Graph.