# Chapter 69. Chromatic Polynomial # Chapter 69. Chromatic Polynomial The chromatic number records the least number of colors needed to color a graph. The chromatic polynomial records more information. It counts how many proper colorings are possible when a fixed number of colors is available. For a graph \(G\), the chromatic polynomial is usually written $$ P_G(k) $$ or $$ \chi_G(k). $$ In this chapter, we write \(P_G(k)\) to avoid confusion with the chromatic number \(\chi(G)\). ## 69.1 Definition Let \(G=(V,E)\) be a finite graph. For a positive integer \(k\), let \(P_G(k)\) denote the number of proper vertex colorings of \(G\) using colors from the set $$ \{1,2,\ldots,k\}. $$ Thus \(P_G(k)\) counts all functions $$ c:V\to \{1,2,\ldots,k\} $$ such that $$ uv\in E \quad \Longrightarrow \quad c(u)\ne c(v). $$ The surprising fact is that this counting function is always a polynomial in \(k\). This polynomial is called the chromatic polynomial of \(G\). The deletion-contraction identity is one standard way to prove polynomiality. ## 69.2 First Examples Let \(N_n\) be the graph with \(n\) vertices and no edges. Since there are no adjacency restrictions, each vertex may receive any of the \(k\) colors. Therefore $$ P_{N_n}(k)=k^n. $$ For the complete graph \(K_n\), all vertices must receive distinct colors. The first vertex has \(k\) choices, the second has \(k-1\), and so on. Hence $$ P_{K_n}(k)=k(k-1)(k-2)\cdots(k-n+1). $$ For the path \(P_n\) with \(n\ge 1\), the first vertex has \(k\) choices. Each later vertex must avoid the color of the previous vertex, so it has \(k-1\) choices. Thus $$ P_{P_n}(k)=k(k-1)^{n-1}. $$ For a tree \(T\) with \(n\) vertices, the same formula holds: $$ P_T(k)=k(k-1)^{n-1}. $$ A tree has no cycles, so after choosing a root, each non-root vertex only needs to avoid the color of its parent. ## 69.3 Relation to Chromatic Number The chromatic polynomial determines the chromatic number. A graph is \(k\)-colorable exactly when $$ P_G(k)>0. $$ Therefore $$ \chi(G)=\min\{k\ge 1:P_G(k)>0\}. $$ The chromatic number gives the first positive integer at which the chromatic polynomial becomes positive. For example, if $$ P_G(1)=0,\qquad P_G(2)=0,\qquad P_G(3)>0, $$ then $$ \chi(G)=3. $$ Thus the chromatic polynomial refines the chromatic number. It does not merely say whether a coloring exists. It counts how many colorings exist for every allowed number of colors. ## 69.4 Deletion and Contraction The most important recursive method for chromatic polynomials uses deletion and contraction. Let \(e=uv\) be an edge of \(G\). The deletion \(G-e\) is the graph obtained by removing the edge \(e\) while keeping all vertices. The contraction \(G/e\) is the graph obtained by identifying \(u\) and \(v\) as a single vertex and then removing the edge \(e\). In simple graphs, parallel edges created by contraction may be replaced by a single edge. Deletion removes a constraint. Contraction identifies the two endpoints of that constraint. These two operations are related because every proper coloring of \(G-e\) falls into one of two classes: | Case | Meaning | |---|---| | \(u\) and \(v\) have different colors | The coloring is a proper coloring of \(G\) | | \(u\) and \(v\) have the same color | The coloring corresponds to a coloring of \(G/e\) | This gives the deletion-contraction formula: $$ P_G(k)=P_{G-e}(k)-P_{G/e}(k). $$ This identity is the standard recursive formula for the chromatic polynomial. It follows by subtracting the colorings of \(G-e\) in which the endpoints of \(e\) receive the same color. ## 69.5 Base Cases The deletion-contraction formula reduces the number of edges. Repeated use eventually reaches graphs with no edges, whose chromatic polynomials are known. If \(G\) has \(n\) vertices and no edges, then $$ P_G(k)=k^n. $$ If \(G\) has a loop, then $$ P_G(k)=0. $$ A loop joins a vertex to itself. Proper coloring would require a vertex to have a color different from itself, which is impossible. These two base cases allow recursive computation. ## 69.6 Example: A Triangle Let \(G=K_3\). Choose an edge \(e\). Then \(G-e\) is a path on three vertices, and \(G/e\) is \(K_2\). Thus $$ P_{K_3}(k)=P_{P_3}(k)-P_{K_2}(k). $$ We know $$ P_{P_3}(k)=k(k-1)^2 $$ and $$ P_{K_2}(k)=k(k-1). $$ Therefore $$ P_{K_3}(k)=k(k-1)^2-k(k-1). $$ Factor: $$ P_{K_3}(k)=k(k-1)\bigl((k-1)-1\bigr). $$ Hence $$ P_{K_3}(k)=k(k-1)(k-2). $$ This agrees with the direct count for a complete graph on three vertices. ## 69.7 Example: A Cycle Let \(C_n\) be a cycle with \(n\ge 3\) vertices. Its chromatic polynomial is $$ P_{C_n}(k)=(k-1)^n+(-1)^n(k-1). $$ This formula explains the parity behavior of cycles. For an even cycle, $$ P_{C_n}(2)=1^n+1=2. $$ There are exactly two proper 2-colorings, corresponding to the two choices of color for the first vertex. For an odd cycle, $$ P_{C_n}(2)=1^n-1=0. $$ Thus an odd cycle is not 2-colorable. ## 69.8 Basic Properties Let \(G\) be a graph with \(n\) vertices, \(m\) edges, and \(c\) connected components. The chromatic polynomial has several important structural properties: | Property | Statement | |---|---| | Degree | \(P_G(k)\) has degree \(n\) | | Leading coefficient | The leading coefficient is \(1\) | | Second coefficient | The coefficient of \(k^{n-1}\) is \(-m\) | | Constant term | If \(n>0\), then \(P_G(0)=0\) | | Lowest nonzero degree | The lowest nonzero power is \(k^c\) | The degree and leading coefficient follow from the fact that, without edge restrictions, there would be \(k^n\) colorings. Edges remove some assignments, but they do not change the leading term. The coefficient of \(k^{n-1}\) records the number of edges with a negative sign. These facts are standard consequences of deletion-contraction and induction on the number of edges. ## 69.9 Disconnected Graphs If a graph is the disjoint union of components $$ G_1,G_2,\ldots,G_r, $$ then colorings of the components may be chosen independently. Therefore $$ P_G(k)=P_{G_1}(k)P_{G_2}(k)\cdots P_{G_r}(k). $$ For example, if \(G\) is the disjoint union of a triangle and an isolated vertex, then $$ P_G(k)=P_{K_3}(k)\cdot k. $$ Thus $$ P_G(k)=k^2(k-1)(k-2). $$ Independence of components turns the chromatic polynomial into a product. ## 69.10 Complete Bipartite Examples Consider the complete bipartite graph \(K_{1,n}\), also called a star. The center has \(k\) choices. Each leaf must avoid the color of the center, but leaves are mutually nonadjacent. Hence $$ P_{K_{1,n}}(k)=k(k-1)^n. $$ More generally, complete bipartite graphs \(K_{m,n}\) have more complicated chromatic polynomials. One can compute them by first choosing the set of colors used on one part, then assigning colors to the other part while avoiding those colors. This illustrates a common theme: symmetry can simplify counting, but dense adjacency between parts still creates nontrivial combinatorics. ## 69.11 Roots of the Chromatic Polynomial A number \(\lambda\) is called a chromatic root of \(G\) if $$ P_G(\lambda)=0. $$ All nonnegative integers smaller than \(\chi(G)\) are chromatic roots. For example, if \(\chi(G)=4\), then $$ P_G(0)=P_G(1)=P_G(2)=P_G(3)=0. $$ Chromatic roots are also studied over the real and complex numbers. Their behavior is subtle and connects graph coloring with algebra, statistical physics, and the Tutte polynomial. For elementary graph theory, the most important roots are the integer roots, since they indicate impossible numbers of colors. ## 69.12 Chromatic Equivalence Two graphs \(G\) and \(H\) are chromatically equivalent if $$ P_G(k)=P_H(k). $$ Chromatically equivalent graphs need not be isomorphic. The chromatic polynomial records important information, but it does not determine the graph completely. A graph is chromatically unique if every graph with the same chromatic polynomial is isomorphic to it. Thus chromatic polynomials give a graph invariant, but not a complete invariant. ## 69.13 Connection with the Tutte Polynomial The chromatic polynomial is a specialization of the Tutte polynomial. The Tutte polynomial is a two-variable graph polynomial that unifies many graph invariants, including the chromatic polynomial, flow polynomial, and number of spanning trees. Deletion-contraction is one of its central principles. This connection places graph coloring inside a broader algebraic framework. In advanced graph theory, the chromatic polynomial is often studied as part of this larger family of deletion-contraction invariants. ## 69.14 Computational Aspects Deletion-contraction gives a conceptually simple algorithm, but it may be computationally expensive. Each edge creates two recursive branches: $$ G-e $$ and $$ G/e. $$ Thus a naive implementation may require exponentially many steps. For special graph classes, faster methods exist. Trees, cycles, complete graphs, and certain decomposable graphs have closed formulas. More generally, algorithms exploit structure such as low treewidth, cut vertices, separations, or chordality. Computing chromatic polynomials belongs to the broader study of graph counting problems, many of which are computationally hard. ## 69.15 Summary The chromatic polynomial \(P_G(k)\) counts proper \(k\)-colorings of a graph. It refines the chromatic number by recording not only whether a coloring exists, but how many such colorings exist. The main ideas are: | Concept | Meaning | |---|---| | \(P_G(k)\) | Number of proper \(k\)-colorings | | Chromatic number | First positive integer \(k\) with \(P_G(k)>0\) | | Deletion | Remove an edge | | Contraction | Identify the endpoints of an edge | | Deletion-contraction | \(P_G(k)=P_{G-e}(k)-P_{G/e}(k)\) | | Chromatic root | Root of \(P_G(k)\) | | Chromatic equivalence | Same chromatic polynomial | The chromatic polynomial is one of the first examples of a graph polynomial. It connects coloring, recursion, algebraic invariants, and enumerative combinatorics. ## 69.16 Exercises 1. Compute the chromatic polynomial of \(K_2\). 2. Compute the chromatic polynomial of \(P_4\). 3. Compute the chromatic polynomial of \(K_4\). 4. Prove that if \(G\) has no edges and \(n\) vertices, then \(P_G(k)=k^n\). 5. Prove that if \(G\) has a loop, then \(P_G(k)=0\). 6. Use deletion-contraction to compute the chromatic polynomial of \(C_4\). 7. Verify that $$ P_{C_n}(k)=(k-1)^n+(-1)^n(k-1) $$ for \(n=3\) and \(n=4\). 8. Prove that if \(G\) is the disjoint union of \(G_1\) and \(G_2\), then $$ P_G(k)=P_{G_1}(k)P_{G_2}(k). $$ 9. Show that the coefficient of \(k^{n-1}\) in \(P_G(k)\) is \(-|E(G)|\). 10. Give two non-isomorphic graphs with the same chromatic polynomial. 11. Prove that \(P_G(k)>0\) if and only if \(G\) is \(k\)-colorable. 12. Compute the chromatic polynomial of the star \(K_{1,n}\). 13. Explain why the chromatic polynomial is a graph invariant. 14. Use deletion-contraction to show that \(P_G(k)\) is a polynomial in \(k\). 15. Find the chromatic roots of \(K_3\).