One kind of graph problem that’s extremely widely used in computer science is called graph coloring. There’s two versions of it, *vertex coloring*, and *face coloring*.
Vertex coloring is the one that’s more widely used. Edge coloring problems are all variations on the following: given a graph *G=(V,E)*, find a mapping of colors to vertices, such than if two vertices are adjacent, they’re assigned different colors?
The variants of the vertex coloring problem are things like:
* What’s the *minimum* number of colors (aka the *chromatic number* of the graph)
that can be used to color a graph?
* Given an integer N, can you find an N-coloring of the graph?
The face coloring problem is more complicated to describe. Suppose you have a *planar* graph. (Remember that that means a graph which can be drawn on a plane with no edges crossing.) Suppose further that the graph has the property that from any vertex v, there is a path through the graph from v to v. Then that graph is called a *map*. For a map drawn on a plane, every edge is part of at least one cycle. The smallest possible cycles – that is, the cycles which are not bisected by any other edges of the graph – are called *countries* or *faces* of the graph. The face coloring problem assigns colors to the *faces* of a graph, so that no two faces that share an edge are the same color. There’s an extremely fascinating proof that any planar map can be face-colored with no more than four colors. We’ll talk about later – it’s the first computer assisted proof that I’m aware of.
But for now, back to vertex coloring. How can we find the chromatic number of an arbitrary graph, G (also written χ(G))?
The one that students often come up with as a first guess – is to find the vertex with highest degree, and that the degree of that vertex will be one smaller than the chromatic number. Alas, it’s not so easy. Take a look at the graph to the right: the maximum degree of a vertex is 4, but it can be 2-colored.
Another common idea is that the chromatic number should be the size of the smallest clique in the graph. Again, no dice – look at the example to the right: the largest clique has degree four, but the graph needs 5 colors. But the largest clique *is* a lower bound.
What we end up with isn’t particularly pretty. There’s no simple way of finding the minimum coloring of a graph. What there *is* is a method of figuring it out from pieces using the lowering bound provided by the the largest clique. It’s based on the idea of a *critical subgraph*.
A critical subgraph C of a graph G is a *proper* subgraph of G – that is, a subgraph of G where C≠G – such that for every proper subgraph B of C, χ(B)<&chi(C). So we can *reduce* G to its largest critical subgraph – and the chromatic number of that subgraph is the same as the chromatic number of G.
So we’ve reduced the problem to identifying the largest critical subgraph. There are a couple of useful properties that can help us:
1. Critical subgraphs are always connected. This should be pretty obvious – if the graph
isn’t connected, then you can color the disconnected subgraphs separately, which
would mean that it’s not critical.
2. In a critical subgraph C with chromatic number χ(C), every node
will have minimum degree χ(C)-1.
But aside from those, we’re mostly on our own. And just to be spiteful, graph colorings also have a nasty property.
Suppose you have a graph G. The number of edges in the smallest cycle in G is called the *girth* of G.
For any x,y≥2, there is a graph with girth x, and chromatic number y. What that means is that you can’t do things like rely on cliques, even as an approximation. Because, for example, a graph with chromatic number 300 isn’t even guaranteed to contain any cliques of size three! Because a 3-clique is a triangle, which is a cycle of size 3… But there are graphs with chromatic number 300, and girth 50.
Just for an example of a graph with this kind of property: the figure to the right is called the Grötzcsh graph. It’s got girth four, but it contains no triangles at all. Try and figure out how many colors it needs.