GRAPH COLORINGS
Consider a graph G. A vertex coloring, or simply a coloring of G is an assignment of colors to the vertices
of G such that adjacent vertices have different colors. We say that G is n-colorable if there exists a coloring of G
which uses n colors. (Since the word “color” is used as a noun, we will try to avoid its use as a verb by
for example, “paint” G rather than “color” G when we are assigning colors to the vertices of G.) The minimum
number of colors needed to paint G is called the chromatic number of G and is denoted by ? (G).
gives an algorithm by Welch and Powell for a coloring of a graph G. We emphasize that this
algorithm does not always yield a minimal coloring of G.