Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 8] GRAPH THEORY 169

for example, “paint”Grather than “color”Gwhen we are assigning colors to the vertices ofG.) The minimum
number of colors needed to paintGis called thechromatic numberofGand is denoted byχ (G).
Fig. 8-24 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 ofG.

Fig. 8-24

EXAMPLE 8.3

(a) Consider the graphGin Fig. 8-25.We use theWelch-PowellAlgorithm 8.4 to obtain a coloring ofG. Ordering

the vertices according to decreasing degrees yields the following sequence:

A 5 ,A 3 ,A 7 ,A 1 ,A 2 ,A 4 ,A 6 ,A 8

Fig. 8-25

The first color is assigned to verticesA 5 andA 1. The second color is assigned to verticesA 3 ,A 4 , andA 8.

The third color is assigned to verticesA 7 ,A 2 , andA 6. All the vertices have been assigned a color, and soG

is 3-colorable. Observe thatGis not 2-colorable since verticesA 1 ,A 2 , andA 3 , which are connected to each

other, must be assigned different colors. Accordingly,χ (G)=3.

(b) Consider the complete graphKnwithnvertices. Since every vertex is adjacent to every other vertex,Kn

requiresncolors in any coloring. Thusχ(Kn)=n.

There is no simple way to actually determine whether an arbitrary graph isn-colorable. However, the
following theorem (proved in Problem 8.19) gives a simple characterization of 2-colorable graphs.