Section 5.4 Graph Coloring
Let's return now to the subject of Example 1.5, assigning frequencies to radio stations so that they don't interfere. The first thing that we will need to do is to turn the map of radio stations into a suitable graph, which should be pretty natural at this juncture. We define a graph \(\GVE\) in which \(V\) is the set of radio stations and \(xy\in E\) if and only if radio station \(x\) and radio station \(y\) are within \(200\) miles of each other. With this as our model, then we need to assign different frequencies to two stations if their corresponding vertices are joined by an edge. This leads us to our next topic, coloring graphs.
When \(\GVE\) is a graph and \(C\) is a set of elements called colors, a proper coloring of \(\bfG\) is a function \(\phi:V\to C\) such that if \(\phi(x)\neq \phi(y)\) whenever \(xy\) is an edge in \(\bfG\text{.}\) The least \(t\) for which \(\bfG\) has a proper coloring using a set \(C\) of \(t\) colors is called the chromatic number of \(\bfG\) and is denoted \(\chi(\bfG)\). In Figure 5.19, we show a proper coloring of a graph using \(5\) colors. Now we can see that our radio frequency assignment problem is the much-studied question of finding the chromatic number of an appropriate graph.
Discussion 5.20.
Everyone agrees that the graph \(\bfG\) in Figure 5.19 has chromatic number at most \(5\text{.}\) However, there's a bit of debate going on about if \(\chi(\bfG)=5\text{.}\) Bob figures the authors would not have used five colors if they didn't need to. Carlos says he's glad they're having the discussion, since all having a proper coloring does is provide them with an upper bound on \(\chi(\bfG)\text{.}\) Bob sees that the graph has a vertex of degree \(5\) and claims that must mean \(\chi(\bfG)=5\text{.}\) Alice groans and draws a graph with \(101\) vertices, one of which has degree \(100\text{,}\) but with chromatic number \(2\text{.}\) Bob is shocked, but agrees with her. Xing wonders if the fact that the graph does not contain a \(\bfK_3\) has any bearing on the chromatic number. Dave's in a hurry to get to the gym, but on his way out the door he says they can get a proper \(4\)-coloring pretty easily, so \(\chi(\bfG)\leq 4\text{.}\) The rest decide it's time to keep reading.
What graph did Alice draw that shocked Bob?
What changes did Dave make to the coloring in Figure 5.19 to get a proper coloring using four colors?
Subsection 5.4.1 Bipartite Graphs
A graph \(\GVE\) with \(\chi(\bfG)\le 2\) is called a \(2\)-colorable graph. A couple of minutes of reflection should convince you that for \(n\geq 2\text{,}\) the cycle \(\bfC_{2n}\) with \(2n\) vertices is \(2\)-colorable. On the other hand, \(\bfC_3\cong \bfK_3\) is clearly not \(2\)-colorable. Furthermore, no odd cycle \(\bfC_{2n+1}\) for \(n\geq 1\) is \(2\)-colorable. It turns out that the property of containing an odd cycle is the only impediment to being \(2\)-colorable, which means that recognizing \(2\)-colorable graphs is easy, as the following theorem shows.
Theorem 5.21.
A graph is \(2\)-colorable if and only if it does not contain an odd cycle.
Proof.
Let \(\GVE\) be a \(2\)-colorable graph whose coloring function partitions \(V\) as \(A\cup B\text{.}\) Since there are no edges between vertices on the same side of the partition, any cycle in \(\bfG\) must alternate vertices between \(A\) and \(B\text{.}\) In order to complete the cycle, therefore, the number of vertices in the cycle from \(A\) must be the same as the number from \(B\text{,}\) implying that the cycle has even length.
Now suppose that \(\bfG\) does not contain an odd cycle. Note that we may assume that \(\bfG\) is connected, as each component may be colored individually. The distance \(d(u,v)\) between vertices \(u,v\in V\) is the length of a shortest path from \(u\) to \(v\text{,}\) and of course \(d(u,u) = 0\text{.}\) Fix a vertex \(v_0\in V\) and define
We claim that coloring the vertices of \(A\) with color \(1\) and the vertices of \(B\) with color \(2\) is a proper coloring. suppose not. Then without loss of generality, there are vertices \(x,y\in A\) such that \(xy\in E\text{.}\) Since \(x,y\in A\text{,}\) \(d(v_0,x)\) and \(d(v_0,y)\) are both even. Let
and
be shortest paths from \(v_0\) to \(x\) and \(y\text{,}\) respectively. If \(x_1\neq y_j\) for all \(1\leq i\leq n\) and \(1\leq j\leq m\text{,}\) then since \(m\) and \(n\) are both even,
is an odd cycle in \(\bfG\text{,}\) which is a contradiction. Thus, there must be \(i,j\) such that \(x_i=y_j\text{,}\) and we may take \(i,j\) as large as possible. (That is, after \(x_i=y_j\text{,}\) the two paths do not intersect again.) Thus,
is a cycle in \(\bfG\text{.}\) How many vertices are there in this cycle? A quick count shows that it has
vertices. We know that \(n\) and \(m\) are even, and notice that \(i\) and \(j\) are either both even or both odd, since \(x_i = y_j\) and the odd-subscripted vertices of our path belong to \(B\) while those with even subscripts belong to \(A\text{.}\) Thus, \(i+j\) is even, so \(n+m-(i+j)+1\) is odd, giving a contradiction.
A graph \(\bfG\) is called a bipartite graph when there is a partition of the vertex \(V\) into two sets \(A\) and \(B\) so that the subgraphs induced by \(A\) and \(B\) are independent graphs, i.e., no edge of \(\bfG\) has both of its endpoints in \(A\) or in \(B\text{.}\) Evidently, bipartite graphs are \(2\)-colorable. On the other hand, when a \(2\)-colorable graph is disconnected, there is more than one way to define a suitable partition of the vertex set into two independent sets.
Bipartite graphs are commonly used as models when there are two distinct types of objects being modeled and connections are only allowed between two objects of different types. For example, on one side, list candidates who attend a career fair and on the other side list the available positions. The edges might naturally correspond to candidate/position pairs which link a person to a responsibility they are capable of handling.
As a second example, a bipartite graph could be used to visualize the languages spoken by a group of students. The vertices on one side would be the students with the languages listed on the other side. We would then have an edge \(xy\) when student \(x\) spoke language \(y\text{.}\) A concrete example of this graph for our favorite group of students is shown in Figure 5.22, although Alice isn't so certain there should be an edge connecting Dave and English.
One special class of bipartite graphs that bears mention is the class of complete bipartite graphs. The complete bipartite graph \(\bfK_{m,n}\) has vertex set \(V=V_1\cup V_2\) with \(|V_1|=m\) and \(|V_2|=n\text{.}\) It has an edge \(xy\) if and only if \(x\in V_1\) and \(y\in V_2\text{.}\) The complete bipartite graph \(\bfK_{3,3}\) is shown in Figure 5.23.
Subsection 5.4.2 Cliques and Chromatic Number
A clique in a graph \(\GVE\) is a set \(K\subseteq V\) such that the subgraph induced by \(K\) is isomorphic to the complete graph \(\bfK_{|K|}\text{.}\) Equivalently, we can say that every pair of vertices in \(K\) are adjacent. The maximum clique size or clique number of a graph \(\bfG\text{,}\) denoted \(\omega(\bfG)\), is the largest \(t\) for which there exists a clique \(K\) with \(|K|=t\text{.}\) For example, the graph in Figure 5.14 has clique number \(4\) while the graph in Figure 5.19 has maximum clique size \(2\text{.}\)
For every graph \(\bfG\text{,}\) it is obvious that \(\chi(\bfG)\ge \omega(\bfG)\text{.}\) On the other hand, the inequality may be far from tight. Before showing how bad it can be, we need to introduce a more general version of the Pigeon Hole Principle. Consider a function \(f\colon X\to Y\) with \(|X| = 2|Y|+1\text{.}\) Since \(|X|>|Y|\text{,}\) the Pigeon Hole Principle as stated in Proposition 4.1 only tells us that there are distinct \(x,x'\in X\) with \(f(x)=f(x')\text{.}\) However, we can say more here. Suppose that each element of \(Y\) has at most two elements of \(X\) mapped to it. Then adding up the number of elements of \(X\) based on how many are mapped to each element of \(Y\) would only allow \(X\) to have (at most) \(2|Y|\) elements. Thus, there must be \(y\in Y\) so that there are three distinct elements \(x,x',x''\in X\) with \(f(x)=f(x')=f(x'')=y\text{.}\) This argument generalizes to give the following version of the Pigeon Hole Principle:
Proposition 5.24. Generalized Pigeon Hole Principle.
If \(f\colon X\to Y\) is a function and \(|X|\geq (m-1)|Y|+1\text{,}\) then there exists an element \(y\in Y\) and distinct elements \(x_1,\dots,x_m \in X\) so that \(f(x_i)=y\) for \(i=1,\dots,m\text{.}\)
We are now prepared to present the following proposition showing that clique number and chromatic number need not be close at all. We give two proofs. The first is the work of J. Kelly and L. Kelly, while the second is due to J. Mycielski.
Proposition 5.25.
For every \(t\ge3\text{,}\) there exists a graph \(\bfG_t\) so that \(\chi(\bfG_t)=t\) and \(\omega(\bfG_t)=2\text{.}\)
Proof.
We proceed by induction on \(t\text{.}\) For \(t=3\text{,}\) we take \(\bfG_3\) to be the cycle \(\bfC_5\) on five vertices. Now assume that for some \(t\ge3\text{,}\) we have determined the graph \(\bfG_t\text{.}\) Suppose that \(\bfG_t\) has \(n_t\) vertices. Label the vertices of \(\bfG_t\) as \(x_1,x_2,\dots,x_{n_t}\text{.}\) Construct \(\bfG_{t+1}\) as follows. Begin with an independent set \(I\) of cardinality \(t(n_t-1)+1\text{.}\) For every subset \(S\) of \(I\) with \(|S|=n_t\text{,}\) label the elements of \(S\) as \(y_1,y_2,\dots,y_{n_t}\text{.}\) For this particular \(n_t\)-element subset attach a copy of \(\bfG_t\) with \(y_i\) adjacent to \(x_i\) for \(i=1,2,\dots,n_t\text{.}\) Vertices in copies of \(\bfG_t\) for distinct \(n_t\)-element subsets of \(I\) are nonadjacent, and a vertex in \(I\) has at most one neighbor in a particular copy of \(\bfG_t\text{.}\)
To see that \(\omega(\bfG_{t+1})=2\text{,}\) it will suffice to argue that \(\bfG_{t+1}\) contains no triangle (\(\bfK_3\)). Since \(\bfG_t\) is triangle-free, any triangle in \(\bfG_{t+1}\) must contain a vertex of \(I\text{.}\) Since none of the vertices of \(I\) are adjacent, any triangle in \(\bfG_{t+1}\) contains only one point of \(I\text{.}\) Since each vertex of \(I\) is adjacent to at most one vertex of any fixed copy of \(\bfG_t\text{,}\) if \(y\in I\) is part of a triangle, the other two vertices must come from distinct copies of \(\bfG_t\text{.}\) However, vertices in different copies of \(\bfG_t\) are not adjacent, so \(\omega(\bfG_{t+1})=2\text{.}\) Notice that \(\chi(\bfG_{t+1})\ge t\) since \(\bfG_{t+1}\) contains \(\bfG_t\text{.}\) On the other hand, \(\chi(\bfG_{t+1})\le t+1\) since we may use \(t\) colors on the copies of \(\bfG_t\) and a new color on the independent set \(I\text{.}\) To see that \(\chi(\bfG_{t+1})=t+1\text{,}\) observe that if we use only \(t\) colors, then by the generalized Pigeon Hole Principle, there is an \(n_t\)-element subset of \(I\) in which all vertices have the same color. Then this color cannot be used in the copy of \(\bfG_t\) which is attached to that \(n_t\)-element subset.
Proof.
We again start with \(\bfG_3\) as the cycle \(\bfC_5\text{.}\) As before we assume that we have constructed for some \(t\ge3\) a graph \(\bfG_t\) with \(\omega(\bfG_t)=2\) and \(\chi(\bfG_t) = t\text{.}\) Again, label the vertices of \(\bfG_t\) as \(x_1,x_2,\dots,x_{n_t}\text{.}\) To construct \(\bfG_{t+1}\text{,}\) we now start with an independent set \(I\text{,}\) but now \(I\) has only \(n_t\) points, which we label as \(y_1,y_2,\dots,y_{n_t}\text{.}\) We then add a copy of \(\bfG_t\) with \(y_i\) adjacent to \(x_j\) if and only if \(x_i\) is adjacent to \(x_j\text{.}\) Finally, attach a new vertex \(z\) adjacent to all vertices in \(I\text{.}\)
Clearly, \(\omega(\bfG_{t+1})=2\text{.}\) Also, \(\chi(\bfG_{t+1})\ge t\text{,}\) since it contains \(\bfG_t\) as a subgraph. Furthermore, \(\chi(\bfG_{t+1})\leq t+1\text{,}\) since we can color \(\bfG_t\) with colors from \(\{1,2,\dots,t\}\text{,}\) use color \(t+1\) on the independent set \(I\text{,}\) and then assign color \(1\) to the new vertex \(z\text{.}\) We claim that in fact \(\chi(\bfG_{t+1})=t+1\text{.}\) Suppose not. Then we must have \(\chi(\bfG_{t+1})=t\text{.}\) Let \(\phi\) be a proper coloring of \(\bfG_{t+1}\text{.}\) Without loss of generality, \(\phi\) uses the colors in \(\{1,2,\dots,t\}\) and \(\phi\) assigns color \(t\) to \(z\text{.}\) Then consider the nonempty set \(S\) of vertices in the copy of \(\bfG_t\) to which \(\phi\) assigns color \(t\text{.}\) For each \(x_i\) in \(S\text{,}\) change the color on \(x_i\) so that it matches the color assigned to \(y_i\) by \(\phi\text{,}\) which cannot be \(t\text{,}\) as \(z\) is colored \(t\text{.}\) What results is a proper coloring of the copy of \(\bfG_t\) with only \(t-1\) colors since \(x_i\) and \(y_i\) are adjacent to the same vertices of the copy of \(\bfG_t\text{.}\) The contradiction shows that \(\chi(\bfG_{t+1})=t+1\text{,}\) as claimed.
Since a \(3\)-clique looks like a triangle, Proposition 5.25 is often stated as “There exist triangle-free graphs with large chromatic number.” As an illustration of the construction in the proof of Mycielski, we again refer to Figure 5.19. The graph shown is \(\bfG_4\text{.}\) We will return to the topic of graphs with large chromatic number in Section 11.6 where we show that are there graphs with large chromatic number which lack not only cliques of more than two vertices but also cycles of fewer than \(g\) vertices for any value of \(g\text{.}\) In other words, there is a graph \(\bfG\) with \(\chi(\bfG)=10^6\) but no cycle with fewer than \(10^{10}\) vertices!
Subsection 5.4.3 Can We Determine Chromatic Number?
Suppose you are given a graph \(\bfG\text{.}\) It's starting to look like it is not easy to find an algorithm that answers the question “Is \(\chi(\bfG)\leq t\text{?}\)” It's easy to verify a certificate (a proper coloring using at most \(t\) colors), but how could you even find a proper coloring, not to mention one with the fewest number of colors? Similarly for the question “Is \(\omega(\bfG)\geq k\text{?}\)”, it is easy to verify a certificate. However, finding a maximum clique appears to be a very hard problem. Of course, since the gap between \(\chi(\bfG)\) and \(\omega(\bfG)\) can be arbitrarily large, being able to find one value would not (generally) help in finding the value of the other. No polynomial-time algorithm is known for either of these problems, and many believe that no such algorithm exists. In this subsection, we look at one approach to finding chromatic number and see a case where it does work efficiently.
A very naïve algorithmic way to approach graph coloring is the First Fit, or “greedy”, algorithm. For this algorithm, fix an ordering of the vertex set \(V=\{v_1,v_2,\dots v_n\}\text{.}\) We define the coloring function \(\phi\) one vertex at a time in increasing order of subscript. We begin with \(\phi(v_1)=1\) and then we define \(\phi(v_{i+1})\) (assuming vertices \(v_1,v_2,\dots,v_i\) have been colored) to be the least positive integer color that has not already been used on any of its neighbors in the set \(\{v_1,\dots v_i\}\text{.}\)
Figure 5.26 shows two different orderings of the same graph. Exercise 5.9.24 demonstrates that the ordering of \(V\) is vital to the ability of the First Fit algorithm to color \(\bfG\) using \(\chi(\bfG)\) colors. In general, finding an optimal ordering is just as difficult as coloring \(\bfG\text{.}\) Thus, this very simple algorithm does not work well in general. However, for some classes of graphs, there is a “natural” ordering that leads to optimal performance of First Fit. Here is one such example—one that we will study again in the next chapter in a different context.
Given an indexed family of sets \(\cgF=\{S_\alpha:\alpha\in V\}\text{,}\) we associate with \(\cgF\) a graph \(\bfG\) defined as follows. The vertex set of \(\bfG\) is the set \(V\) and vertices \(x\) and \(y\) in \(V\) are adjacent in \(\bfG\) if and only if \(S_x\cap S_y \neq\emptyset\text{.}\) We call \(\bfG\) an intersection graph. It is easy to see that every graph is an intersection graph (Why?), so it makes sense to restrict the sets which belong to \(\cgF\text{.}\) For example, we call \(\bfG\) an interval graph if it is the intersection graph of a family of closed intervals of the real line \(\reals\text{.}\) For example, in Figure 5.27, we show a collection of six intervals of the real line on the left. On the right, we show the corresponding interval graph having an edge between vertices \(x\) and \(y\) if and only if intervals \(x\) and \(y\) overlap.
Theorem 5.28.
If \(\GVE\) is an interval graph, then \(\chi(\bfG)=\omega(\bfG)\text{.}\)
Proof.
For each \(v\in V\text{,}\) let \(I(v)=[a_v,b_v]\) be a closed interval of the real line so that \(uv\) is an edge in \(\bfG\) if and only if \(I(u)\cap I(v)\neq\emptyset\text{.}\) Order the vertex set \(V\) as \(\{v_1,v_2,\dots v_n\}\) such that \(a_1\leq a_2\leq \cdots \leq a_n\text{.}\) (Ties may be broken arbitrarily.) Apply the First Fit coloring algorithm to \(\bfG\) with this ordering on \(V\text{.}\) Now when the First Fit coloring algorithm colors \(v_i\text{,}\) all of its neighbors have left end point at most \(a_i\text{.}\) Since they are neighbors of \(v_i\text{,}\) however, we know that their right endpoints are all at least \(a_i\text{.}\) Thus, \(v_i\) and its previously-colored neighbors form a clique. Hence, \(v_i\) is adjacent to at most \(\omega(\bfG)-1\) other vertices that have already been colored, so when the algorithm colors \(v_i\text{,}\) there will be a color from \(\{1,2,\dots,\omega(\bfG)\}\) not already in use on its neighbors. The algorithm will assign \(v_i\) the smallest such color. Thus, we never need to use more than \(\omega(\bfG)\) colors, so \(\chi(\bfG)=\omega(\bfG)\text{.}\)
A graph \(\bfG\) is said to be perfect if \(\chi(\bfH)=\omega(\bfH)\) for every induced subgraph \(\bfH\text{.}\) Since an induced subgraph of an interval graph is an interval graph, Theorem 5.28 shows interval graphs are perfect. The study of perfect graphs originated in connection with the theory of communications networks and has proved to be a major area of research in graph theory for many years now.