A university is organizing a conference on undergraduate research that will contain student presentations. Prior to the conference, the participants selected which presentations they plan to attend and the conference organizers would like to schedule the presentations (each of the same time length) so that participants can attend all the presentations they selected and the presentation they will deliver. The university has many rooms to use for the conference and can therefore schedule presentations in parallel. The organizers would like to minimize the time for all presentations to complete. This scheduling problem can be described using a graph as follows. Let be the presentations. The presentations and are adjacent if there is a participant who will attend both and . Let be the number of time slots during which parallel presentations will be held. The scheduling problem is then to assign to each presentation a time slot so that adjacent presentations receive a distinct time slot.
The basics
We begin with the definition of a graph coloring.
Let be a graph and let be a positive integer. A -coloring of the graph is a function such that if and are adjacent then . If has a -coloring then we say that is -colorable. The set of numbers are called the colors of the coloring .
For each graph, find a coloring.
is two 's connected by a bridge
Suppose that is a -coloring of . Let and assume for each . By definition, consists of vertices that are colored with the same color and we call a color class induced by . By definition of a coloring, any two vertices in are not adjacent. In general, a non-empty subset is called an independent set if no two vertices in are adjacent. Hence, if are the color classes induced by then each non-empty color class is an independent set. Moreover, since each vertex receives a color, is a partition of the vertex set .
Obtain a coloring of the given graph and list the color classes.
If is -colorable then it is also -colorable for any (prove this!). Given a graph , it is natural then to ask for the smallest integer such that is -colorable. This number is given a special name.
The chromatic number of , denoted by , is the smallest integer such that is -colorable.
It is clear that if has at least one edge then .
Prove that
Solution: Label the vertices of so that and recall that we must have . Suppose that is odd. Define as follows: let if is odd, let if is even, and let . Then is a coloring. Suppose by contradiction that is a coloring of . We can assume without loss of generality that . Then if is even. Since , and is even, we must have . However, and thus is not a coloring. Hence, if is odd.
Now suppose that is even. Then define by if is odd and if is even is a coloring. Hence, and thus since is not the empty graph.
Compute the chromatic numbers of the wheels and . What about for any ?
Prove that .
Prove that if then .
Bounds on the chromatic number
Given a graph with vertices, we may color each vertex with a distinct color and obtain a -coloring. This shows that . It is clear that a coloring of must have at least colors and thus . On the other hand, the empty graph can be colored (properly) with only one color and thus . However, if has at least one edge then . We therefore have the following.
For any graph not equal to or , we have that .
A lower bound on is obtained through the notion of a clique and clique number of a graph.
A subset is called a clique if all vertices in are mutually adjacent. In other words, is a clique if and only if is a complete graph. The clique number of a graph is the cardinality of a largest clique in , and is denoted by .
What is the clique number of a cycle? More generally, of a bipartite graph?
If is a clique in then any coloring of must assign distinct colors to vertices in , and thus any coloring of must contain at least colors. We therefore obtain the following.
For any graph we have .
As an example of a graph for which , take a cycle of odd length. In Example 3.3 we showed that if is odd; on the other hand for all .
Recall that is an independent set if no two vertices in are adjacent. The independence number of , denoted by , is the cardinality of a largest independent set in .
Prove that .Solution: Let be an independent set with cardinality . Then is a clique in and therefore . Conversely, suppose that is a largest clique in . Then is an independent in . Therefore, . This proves the claim.
Suppose that are the color classes of a -coloring in . Then for all . It follows that
We may take and therefore
Suppose now that is a largest independent set in , and thus . Color all vertices in with color . The remaining vertices may be colored with distinct colors, say . This produces a coloring of . Therefore,
To summarize:
For every graph it holds that
We now describe a greedy algorithm that always produces a coloring. Let be an ordering of the vertices of . For each vertex , let be the number of vertices adjacent to that are lower in the order, that is, . It is clear that and thus . Hence, for each vertex , the number of neighbors of that are lower in the order is at most .
With the notation above, it holds that . In particular, .
Consider the set of colors . Color with the color . Suppose that have been colored so that no adjacent vertices received the same color. Now consider . The number of vertices adjacent to that have already been colored is at most . Hence, we can color with or with a lower color and thereby produce a proper coloring of the vertices . By induction, this proves that can be colored with at most colors.
The following example shows that the number of colors needed in the greedy algorithm depends on the chosen ordering of the vertices.
Consider the cycle with vertices labelled in two different ways as shown below. Apply the greedy coloring algorithm in each case.
Verify that if is a complete graph or a cycle with an odd number vertices then the inequality in Theorem 3.2.5 is an equality when .
It turns out that complete graphs and cycles of odd length are the only graphs for which equality holds in Theorem 3.2.5. This is known as Brook's theorem.
If is a connected graph that is neither a complete graph or an odd cycle then .
In this exercise, we are going to prove that there is a labelling of the vertices of so that the greedy algorithm uses exactly colors. Suppose that are the color classes of some chromatic coloring of and let for . Label the vertices of so that the first vertices are in , the next vertices are in , and repeatedly until the last vertices are in . Explicitly, , , until finally . Since is an independent set, we can color all vertices in with color 1. Now consider the vertices in . If is adjacent to a vertex in then we must color with color 2, otherwise we can color with color 1. Since is an independent set, after this re-coloring the vertices in receiving the same color are not adjacent. Now consider the vertices in . For , we can choose one of the colors to color ; for example, if is not adjacent to any vertex in then color with color 1, if is not adjacent to any vertex in then color with color 2; otherwise we need to color with 3. Since is an independent set, the vertices in receiving the same color are not adjacent. By induction, suppose that we have colored all vertices up to and including . Any vertex in is adjacent to at most colored vertices, all of which have been colored with one of . Hence, to color we can choose the smallest available color from . This proves that the greedy algorithm uses at most colors. Since , the greedy algorithm uses exactly colors. We note that, in general, the new coloring will produce distinct color classes.
As an example, consider the chromatic 4-coloring of the graph in Figure 3.1. The coloring is indeed chromatic since . The color classes are , , , and . Starting with the labelling shown in Figure 3.1, and performing the greedy algorithm, we obtain a new coloring with color classes , , , and . Note that this produces a distinct chromatic coloring of .
A labelling of from a chromatic coloring for which the greedy algorithm produces a (new) chromatic coloring
Let be a -chromatic graph, that is, . Show that in every -coloring of , there exists at least one vertex in each color class that is adjacent to at least one vertex in each of the other color classes. Deduce that has at least vertices with degree at least . Solution: Let be the color classes of a -chromatic coloring of . Suppose by contradiction that some color class contains no vertex that is adjacent to at least one vertex in each of the other classes. We can assume without loss of generality that this color class is . We will re-color the vertices in to produce a coloring as follows. Since each is non-adjacent to at least one of the other color classes, there is a color available in to re-color . Hence, this re-coloring of produces a coloring which is a contradiction since . Thus, every color class has at least one vertex adjacent to the other color classes. This clearly implies the existence of vertices with degree at least .
The following theorem gives in many cases a better upper bound than Brook's theorem \cite{HW:67}.
Let be a graph and let denote the largest eigenvalue of the adjacency matrix of . Then . Moreover, equality holds if and only if is a complete graph or an odd cycle.
If has a large clique then is also large since . In every non-trivial clique (i.e., a clique containing at least 3 vertices), there is a triangle. Hence, if has no triangles then , and thus it is reasonable to investigate whether graphs with no triangles have small . Surprisingly, this is not the case.
For any , there exists a -chromatic graph with no triangles.
The proof is by induction on . If then is a triangle-free -chromatic graph and when then is a triangle-free -chromatic graph. Assume that is a triangle-free chromatic graph and let be the vertices of . Add new vertices and , and connect to and also to the neighbors of , for . Denote the resulting graph by . Any -coloring of can be extended to a -coloring of by coloring with the same color as , for , and coloring with . Hence, . Assume that is -colorable and suppose without loss of generality that is colored with . Then no vertex is colored with . If is colored with then recolor it with the same color as . Since no vertex is colored with , this produces a -coloring of , which is a contradiction. Hence, . We now prove is triangle-free. Since is an independent set in and no vertex is adjacent to , any triangle in (if any) must consist of two vertices and and one vertex . But if are the vertices of a triangle in then and implies that and and thus are the vertices of a triangle in , which is a contradiction. Hence, is triangle-free and the proof is complete.
The punchline of Theorem 3.2.8 is that the chromatic number can get arbitrarily high even if we limit in the strongest way the size of the largest clique.
The Chromatic Polynomial
For each non-negative integer let be the number of distinct -colorings of . The function was introduced by George Birkhoff (1912) in his quest to prove the Four Color Theorem for planar graphs. Let us clarify what we mean by ``distinct colorings''. Recall that a -coloring of is a function . Hence, and are two distinct -colorings if for at least one vertex , that is, at least one vertex of is colored differently in the colorings and . Before we proceed we note that if has at least one vertex then since there is no way to color the vertices of a graph with colors.
For each graph shown below, produce two distinct colorings using and colorings, respectively.
Let us prove that is an invariant.
If and are isomorphic graphs then for every integer .
This is left as an important exercise.
Consider the empty graph and let . We can color vertex with any of the colors , we can color with any of the colors , etc. Any such -coloring is and thus the number of -colorings of is .
Now consider the other extreme, i.e., consider . If then there are no -colorings of , and thus for . Suppose then that . We start by coloring by choosing any of the colors. Then we have color choices to color , then color choices to color , and inductively we have color choices for . Hence, the number of -colorings of is
Notice that our formula for is a polynomial function in , as was for . Now, the polynomial expression we obtained for has the property that if which is exactly the statement that there are no colorings of using less than colors. If for example then we obtain
For any graph it holds that
Equivalently, if and only if .
If then there is a -coloring of and thus by definition of we have . If on the other hand then since we can color with colors then we can certainly color with colors and thus . By definition of , if then there are no -colorings of and thus .
Directly finding for anything other than or as we did above quickly becomes a non-trivial exercise. There is, as we describe below, a recursive reductive approach to compute . Before we state the relevant theorem, we need some notation. If is an edge recall that is the graph obtained by deleting the edge . We define the graph as the graph obtained by removing the edge , identifying the end-vertices of , and eliminating any multiple edges.
Draw any graph , pick an edge , and draw .
For any graph and it holds that
We consider the number of colorings of . We partition the of colorings of into two types. The first are the colorings in which the end-vertices of are colored differently. Each such coloring is clearly a coloring of . Hence, there are such colorings. The second are the colorings in which the end-vertices of are colored the same. Each such coloring is clearly a coloring of . The number of such colorings is . Hence, the total number of colorings of is
and the claim follows.
The upshot of the reduction formula
is that has one less vertex and edge than and has one less edge and might have more components than . Regarding the latter case, the following will be useful.
If then
By definition, . The number of ways to properly color the vertices in is and the number of ways to properly color the vertices in is . Since both colorings can be done independently, the result follows.
Find the chromatic polynomials of the graphs shown in Figure 3.2.
Graphs for Example 3.16
We now prove some basic properties of the function .
Let be a graph of order . The function is a monic polynomial of degree with integer coefficients.
We induct over the number of edges. If has no edges then and we showed above that . This proves the base case. Now suppose the claim holds for all graphs with no more than edges and let be a graph with edges and vertices. Pick any edge . By the chromatic reduction theorem, . The graph contains edges and vertices, and has vertices and no more than edges. By induction, is a monic polynomial of degree with integer coefficients and is a monic polynomial of degree with integer coefficients. Hence, is a monic polynomial of degree with integer coefficients.
Based on the result of Theorem 3.3.5, we call the chromatic polynomial of the graph .
For any graph , the chromatic polynomial can be written in the form
where .
We induct over the number of edges. If is the empty graph then clearly satisfies the claim. Suppose the claim is true for all graphs with no more than edges and let be a graph with edges and vertices. By induction, we may write that
where and
where . Then
and this proves the claim.
We now prove an important property about the coefficients of when is connected but first we need the following lemma.
Suppose that contains vertices. If is connected then is connected for any .
The proof is left as an exercise.
If is connected then the coefficients of in are all non-zero.
The proof is by induction on the number of edges. If then and it is not hard to see that . Hence, the claim holds for . Assume that the claim holds for all connected graphs with at most edges and let be a graph with edges and vertices. If then has at most edges and thus by induction the coefficients of in are non-zero. Using the notation in the proof of Lemma 3.3.6, we may write that where . Again, using the notation in the proof of Lemma 3.3.6 we may write
where . This proves that the coefficients of in are all non-zero.
We now consider the case of disconnected graphs.
If and has vertices then
Moreover, for all .
By Proposition 3.3.4 we have
Since each has no constant term, the smallest possible non-zero term in is . By Theorem 3.3.8, the coefficient of in each of is non-zero. The coefficient of in is the product of the coefficients of in for . Hence, the coefficient of in is non-zero.
We now prove that each for . The proof is by induction on the number of vertices. The case is trivial. Assume that the claim holds for all graphs with at most vertices and let be a graph with vertices and components . Then is a graph with vertices and components and is a graph with vertices and at least components. We may therefore write that where and by induction where . Therefore,
and since and for this proves the claim.
We now discuss some of the properties of the roots of a chromatic polynomial. Let and suppose that is a non-negative inter. If then there are no colorings -colorings and therefore . Thus, there exists integers , for , and a polynomial not having as roots such that
If then and therefore . Thus, has no non-negative integer roots. Any negative integer roots of would therefore be supplied entirely by . However, the following shows that will not happen.
The chromatic polynomial of any graph does not contain any roots in .
By Proposition 3.3.4, we can sssume that is connected. Thus
where (by Theorem 3.3.8). Suppose that and thus . Then
Since and for all , it follows that .
Many graphs, however, have chromatic polynomials with complex roots.
The chromatic polynomial of the graph in Figure 3.3 is which has complex roots .
Graph with complex chromatic roots
For any graph of order and edges, the coefficient of in is .
The proof is by induction on the number of edges. If has edges and vertices then is the union of and . Therefore,
and the claim follows. Assume that the claim holds for all graphs with at most edges and suppose that has edges and vertices. By the proof of Lemma 3.3.6, we have
where . By induction and the claim holds.
A graph with vertices is a tree if and only if
We first prove that if is a tree on vertices then . The proof is by induction on . If then and the claim follows. Assume by induction that the claim holds for all trees with at most vertices and let be a tree with vertices. Since is a tree, it has a leaf whose neighbor is say . Let . By the chromatic reduction theorem, . The graph is a tree with vertices and thus . On the other hand, is the union of a tree on vertices and . Thus, by induction we have . Therefore,
and the claim follows.
Now suppose that has vertices and . Expanding we obtain
and thus by Propositon 3.3.11 we have . Since the coefficient of in is non-zero, by Theorem 3.3.9 it follows that is connected. Hence, is a tree.
Use the chromatic reduction theorem to prove that the chromatic polynomial of a cycle is
Solution: For we have
and thus as claimed. Assume that the claim holds for and consider . For any we have that is and is . Using the chromatic reduction theorem, the induction hypothesis, and the fact that is a tree we obtain
and this completes the proof.
Show that . Use this to find the chromatic polynomial of the wheel graph .
Exercises
In this question you are going to prove that the chromatic polynomial is an isomorphism invariant.
Suppose that and are isomorphic and is an isomorphism. Suppose that is a coloring of . Define the function by . Prove that is a coloring of .
Deduce from part (a) that .
Now explain why .
Conclude.
Let be the color classes of a coloring of . We will say that is adjacent to if there exists and such that .
Give an example of a connected graph and a coloring of that graph that produces color classes for which there exists some and (distinct) that are not adjacent.
Prove that if are the color classes of a chromatic coloring of a graph (that is, ) then is adjacent for every distinct color classes and .
Deduce from part (b) that the number of edges in a graph is at least .
Provide a proof of Lemma 3.3.7, that is, prove that if is connected then is connected for any .
Find if . (Hint: is planar so draw it that way.)
Explain why is not the chromatic polynomial of any graph . (Hint: \href{https://www.wolframalpha.com/}{WolframAlpha})
For any graph , let be the number of triangles in . If prove that
where . (Hint: Induct over the number of edges and use the Chromatic Reduction theorem. You will also need Proposition 3.3.11.)
