Graph theory is one of the most beautiful and accessible areas of
mathematics, and the problem of
graph coloring is one of the most fascinating (and frustrating) problems in graph theory. Here's how it goes. You are given a
graph G and a
set C of k
colors. The problem is to associate with each
vertex of G a color in C in such a manner that no two vertices of G which are joined by an
edge are associated with the same color. If it is possible to color the
vertices of G in this way using colors from C, we say that G is k-colorable and that C provides a k-coloring for G.
The chromatic number of G, denoted χ(G), is the smallest positive integer k such that G is k-colorable.
Suppose G is a graph with n vertices. Then, if we took the set C := {1,2,...,n} of n "colors" and assigned to each of the n vertices of G a different color from C, we would obtain an n-coloring for G. This tells us that χ(G) ≤ n.
If G is a graph with at least one edge, then χ(G) > 1. This is because there are at least two adjacent vertices in G which have to be associated with two different colors. Thus, we see that if χ(G) = 1, then G is a vertex graph.
If G is a graph of order n (i.e. G has n vertices), then χ(G) = n if and only if G is a complete graph.
It is easy to see that χ(G) = n if G is a complete graph because, assuming that n > 1, every vertex of G is adjacent to every other vertex and if G had an (n-1)-coloring then two of the vertices of G would be assigned the same color, which violates the statement of the problem since they are adjacent. If n = 1, then clearly χ(G) is 1, so we are done proving one direction of the statement.
For the converse, let G be a graph of order n that is not complete. Then, there are two vertices u and v of G which are not adjacent. Let C := {1,2,...,n-1}. If we associate with both u and v the color n-1, we can associate with each of the remaining n-2 vertices in G each of the n-2 remaining colors in C to obtain an (n-1)-coloring of G. So if G is not complete, then χ(G) < n. This means that if χ(G) = n, G is complete and we are done.
Another observation that we can make is this: If H is any subgraph of G, then χ(H) ≤ χ(G) because we require at least as many colors to color G as we do to color H. This leads us to the statement that the chromatic number of G is bounded below by the clique number of G (the order of the largest clique, aka. complete graph, contained in G).
Let us look at the chromatic numbers of certain special types of graphs. We shall from now on assume that G has at least 2 vertices.
If G is an arc, then χ(G) = 2. If we let C := {0,1} be our set of colors, we can start at one end of the arc G, color it 0, and then switch colors as we move along the arc.
If G is a circuit (also called a cycle), then the chromatic number of G depends on the parity of its order. If G has even order, then we can show that χ(G) = 2 using an argument like the previous one. If G has odd order, then χ(G) = 3 since using our previous algorithm will result in the vertex that we picked to begin with and the last one that we look at to have the same color.
We also have that G is a bipartite graph if and only if χ(G) = 2.
If χ(G) = 2, then we can partition the vertices according to their color and due to the nature of the graph coloring problem, the edges in G will only go between vertices of different color. Conversely, if G is bipartite with the sets U and V partitioning its vertex set, we can associate each of the vertices in U with one color, and each of the vertices in V with another color to get a 2-coloring of G. This leads to another way of looking at the graph coloring problem --- given a graph G and a positive integer k, is there a partition of the vertex set of G into k sets such that no two elements in one of the sets in the partition are adjacent?
We can get another bound on the chromatic number of a graph G using the maximal degree (or valency) of the vertices in G. Suppose G is a graph in which the maximum degree of any vertex is d. Then, χ(G) ≤ d + 1.
Basically, if G has order n, then we can write the vertices of G as v_1, v_2, ..., v_n. If we go through the vertices in ascending order and assign to each vertex a color from C := {1,2,...,d+1} which hasn't been assigned to any of the previous vertices which are adjacent to it, there will be at least one color at each step that we can assign because the vertex that we look at at each step can be adjacent to at most d of the previous vertices and |C| = d+1. So C will give us a (d+1)-coloring of G and therefore χ(G) ≤ |C| = d+1.
This result was expanded upon in 1941 by R.L. Brooks as follows:
Brooks' Theorem: If G is neither a complete graph nor a circuit of odd order, and if the maximal degree of any vertex in G is d, then χ(G) ≤ d.
Another concept associated with the graph coloring problem is that of the chromatic polynomial. The chromatic number of a graph tells us what the smallest number k is for which a k-coloring of the graph exists. Given a positive integer k, the chromatic polynomial counts the number of k-colorings of a graph. The chromatic number of a graph is the smallest natural number that is not a root of the chromatic polynomial. From this, we can tell that the degree of the chromatic polynomial of a graph G is at least χ(G) - 1.
To get a feeling for how important this stuff is, consider the fact that the infamous Four Color Theorem merely (haha) states that the chromatic number of a planar graph is at most 4.
A more computational view of the graph coloring problem is to just view it as a very special type of constraint satisfaction problem. The problem of finding χ(G) given a graph G is NP-complete. In fact, given a graph G, even the problem of figuring out whether G is 3-colorable is NP-complete (as is the problem of figuring out if G is k-colorable for k > 2). In order to tell if a graph G is 3-colorable, a computer would basically have to find a 3-coloring of G, which can get pretty ugly and is NP-hard. The reason it isn't NP-hard, though, is that given an alleged 3-coloring of a graph G, one just has to check that the end vertices of each edge of the graph are colored differently, so the checking algorithm is polynomial in the number of edges of G.
Anywho, this is just a glimpse of all the fun that you could have playing with the graph coloring problem, but maybe it'll get some of you guys interested enough in it to mess with it some more, and possibly come up with some cool results. Enjoy! :)