Colorings as Upper-Bound Certificates
A proper vertex coloring assigns colors to the vertices of a graph so that adjacent vertices receive different colors. Finding a coloring with a small number of colors gives evidence that the graph can be colored efficiently. But a coloring alone does not show that fewer colors are impossible. To certify an exact answer, we need both an upper bound from a coloring and a lower bound from a separate argument.
Throughout, graphs are finite and simple. A set of vertices is independent if no two of its vertices are adjacent. The independence number \(\alpha(G)\) is the largest size of an independent set in \(G\).
Some definitions allow a \(k\)-coloring to use fewer than \(k\) colors. Either convention gives the same minimum. When we say a coloring uses \(k\) colors, we mean that exactly \(k\) distinct colors appear. Each color class—the set of vertices assigned one particular color—is independent, because an edge cannot have both endpoints in that class. Consequently, a proper coloring divides the vertices into independent sets.
We call the coloring an upper-bound certificate: it provides an explicit assignment that can be checked against the edges. A lower-bound certificate is a valid argument that fewer than some stated number of colors cannot work. The two bounds meet when they give the same number.
A Lower Bound from Independent Sets
Proof. Let \(n=|V(G)|\), let \(\alpha=\alpha(G)\), and consider any proper coloring of \(G\) using \(r\) colors. Each of its \(r\) color classes is independent, so each class has at most \(\alpha\) vertices. Since the classes partition the \(n\) vertices, \(n\le r\alpha\). Because \(\alpha\ge1\), this implies \(r\ge n/\alpha\), and since \(r\) is an integer, \(r\ge\lceil n/\alpha\rceil\). This holds for every proper coloring, including one using the minimum number of colors, so the stated bound follows. \(\square\)
The theorem turns a bound on the size of independent sets into a bound on the number of color classes required. To use it, we must justify the claimed value or upper bound for \(\alpha(G)\); merely estimating it without proof does not certify anything. If a coloring uses exactly \(\lceil |V(G)|/\alpha(G)\rceil\) colors, the theorem and the coloring together determine \(\chi(G)\).
Proof. The lower-bound proof says that every proper coloring uses at least \(L\) colors, so in particular the minimum number satisfies \(\chi(G)\ge L\). The exhibited proper coloring uses \(U\) colors, so the minimum satisfies \(\chi(G)\le U\). With \(L=U\), both inequalities force \(\chi(G)=L\). \(\square\)
Worked Certificates
Worked Example: An Exact Bound for a Five-Vertex Graph
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\). We will show that \(\chi(G)=3\).
First, assign color A to vertices \(1,3\), color B to vertices \(2,4\), and color C to vertex \(5\). The edges \(12,23,34,45,51\) have endpoint colors A–B, B–A, A–B, B–C, and C–A, respectively. Thus every edge has differently colored endpoints, so this is a proper coloring using three colors. It proves \(\chi(G)\le3\).
For a lower bound, we verify that \(\alpha(G)=2\). The set \(\{1,3\}\) is independent, so \(\alpha(G)\ge2\). To rule out an independent set of size three, list all ten three-vertex subsets. Each contains an edge: \(123\) contains \(12\); \(124\) contains \(12\); \(125\) contains \(12\); \(134\) contains \(34\); \(135\) contains \(51\); \(145\) contains \(45\); \(234\) contains \(23\); \(235\) contains \(23\); \(245\) contains \(45\); and \(345\) contains \(34\). Therefore no three-vertex set is independent, and \(\alpha(G)=2\).
Here \(n=5\), so the theorem gives \(\chi(G)\ge\lceil5/2\rceil=3\). The coloring gives \(\chi(G)\le3\). Together, \(3\le\chi(G)\le3\), and therefore \(\chi(G)=3\).
Check: the three color classes have sizes \(2,2,1\), summing to \(2+2+1=5\), as required to cover all vertices. The lower-bound calculation uses \(\alpha(G)=2\), not an assumed size: the independent pair and the list of all triples establish that value.
Worked Example: A Two-Color Certificate
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,14,15\}\). The assignment \(c(1)=\mathrm{red}\) and \(c(2)=c(3)=c(4)=c(5)=\mathrm{blue}\) is proper: each of the four edges joins vertex \(1\) to a blue vertex. Thus \(\chi(G)\le2\).
To apply the independent-set bound, consider any independent set. If it contains vertex \(1\), it cannot contain any of \(2,3,4,5\), because all four are adjacent to \(1\); in that case its size is at most \(1\). If it does not contain \(1\), it is a subset of \(\{2,3,4,5\}\), so its size is at most \(4\). The set \(\{2,3,4,5\}\) is independent, so \(\alpha(G)=4\). Since \(n=5\), the bound is \(\chi(G)\ge\lceil5/4\rceil=2\).
The upper and lower bounds match, giving \(\chi(G)=2\). There is also a direct check that one color cannot suffice: the edge \(12\) requires different colors at its endpoints. This independently verifies that \(\chi(G)\ge2\).
Check: all four listed edges have one red endpoint and one blue endpoint. The two bounds are \(\chi(G)\le2\) and \(\chi(G)\ge2\), so the answer is exactly \(2\).
Worked Example: A Coloring That Is Not Optimal
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,34\}\). Assign four different colors, one to each vertex. This is a proper coloring, so it proves only that \(\chi(G)\le4\). A less wasteful assignment gives red to \(1,3\) and blue to \(2,4\). Edge \(12\) has colors red and blue, and edge \(34\) has colors red and blue, so this is a proper two-coloring and \(\chi(G)\le2\).
For the lower bound, an independent set can contain at most one of \(1,2\), since \(12\) is an edge, and at most one of \(3,4\), since \(34\) is an edge. It therefore has size at most \(1+1=2\). The set \(\{1,3\}\) is independent, so \(\alpha(G)=2\). Now \(n=4\), and the theorem gives \(\chi(G)\ge\lceil4/2\rceil=2\). Combining the bounds yields \(\chi(G)=2\).
Check: the two color classes are \(\{1,3\}\) and \(\{2,4\}\). Neither contains an edge, and together they contain all four vertices. The original four-color assignment was valid, but its upper bound \(4\) did not match the lower bound \(2\), so it did not certify optimality.
Common Pitfalls and How to Avoid Them
Mistake: treating a valid coloring as proof of optimality. For the graph in the last example, the assignment of four distinct colors is proper. The incorrect conclusion “therefore \(\chi(G)=4\)” confuses \(\chi(G)\le4\) with equality. The correction is to seek a lower bound: the independent-set argument gives \(\chi(G)\ge2\), and the displayed two-coloring gives \(\chi(G)\le2\), so \(\chi(G)=2\).
Mistake: using an independent-set bound without establishing the independence number. The theorem uses \(\alpha(G)\), the size of a largest independent set, not just the size of an independent set someone has happened to find. If you know only that \(G\) contains an independent set of size \(s\), this establishes \(\alpha(G)\ge s\), not \(\alpha(G)=s\). Since a larger \(\alpha(G)\) can weaken the lower bound, a certificate must justify the upper bound on independent-set size that it uses.
Remember the two directions. A coloring proves “at most”; a lower-bound argument proves “at least.” An exact chromatic number is certified when these conclusions agree. If they do not agree, the bounds may still be correct, but they have not yet settled the answer.
Check Your Understanding
For each question, distinguish what a coloring proves from what a lower-bound argument proves.
- A graph has \(9\) vertices and independence number \(3\). What lower bound on its chromatic number follows from the theorem?
- Suppose a proper coloring uses \(4\) colors and a separate argument proves that no proper coloring can use fewer than \(4\). What is the chromatic number, and which argument supplies each inequality?
- For the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,34\}\), explain why a coloring with four distinct colors does not prove that the chromatic number is \(4\).
- Why must each color class in a proper coloring be an independent set?
- For a nonempty graph with \(n\) vertices and \(\alpha(G)=a\), explain why \(r\) color classes can cover at most \(ra\) vertices.