ABSTRACT
A coloring of the vertices of a graph G is an assignment of colors to the vertices. A coloring is proper if adjacent vertices always have different colors. We shall usually
be interested only in proper colorings. It is clear that the complete graphKn requires n distinct colors for a proper coloring. Any bipartite graph can be colored in just two colors. More formally,
DEFINITION 13.1: An m-coloring of G is a mapping from V (G) onto the set {1, 2, . . . ,m} of m “colors”. The chromatic number of G is χ(G), the minimum value m such that G has a proper m-coloring. If χ(B) = m, G is then said to be m-chromatic.
