11.7. Coloring 321
coloring is called itschromatic number, .G/.
SoGisk-colorable iff .G/k.
In general, trying to figure out if you can color a graph with a fixed number of
colors can take a long time. It’s a classic example of a problem for which no fast
algorithms are known. In fact, it is easy to check if a coloring works, but it seems
really hard to find it. (If you figure out how, then you can get a $1 million Clay
prize.)
11.7.2 Some Coloring Bounds
There are some simple properties of graphs that give useful bounds on colorability.
The simplest property is being a cycle: an even-length closed cycle is 2-colorable,
and since by definition it must have some edges, it is not 1-colorable. So
.Ceven/D2:On the other hand, an odd-length cycle requires 3 colors, that is,
.Codd/D3: (11.3)You should take a moment to think about why this equality holds. Another simple
example is a complete graphKn:
.Kn/Dnsince no two vertices can have the same color.
Being bipartite is another property closely related to colorability. If a graph is
bipartite, then you can color it with 2 colors using one color for the nodes on the
“left” and a second color for the nodes on the “right.” Conversely, graphs with
chromatic number 2 are all bipartite with all the vertices of one color on the “left”
and those with the other color on the right. The graphs with chromatic number 1
are the graphs with no edges—theempty graphs. Empty graphs are bipartite as
long they have at least two vertices: a graph with only one vertex is not bipartite
because its vertex set cannot be partitioned into twononemptysubsets. In short:
Lemma 11.7.2.A graph with more than one vertex is 2-colorable iff it is bipartite.
The chromatic number of a graph can also be shown to be small if the vertex
degrees of the graph are small. In particular, if we have an upper bound on the
degrees of all the vertices in a graph, then we can easily find a coloring with only
one more color than the degree bound.
Theorem 11.7.3.A graph with maximum degree at mostkis.kC1/-colorable.