From Proper Colorings to Chromatic Polynomials

From a Coloring Count to a Polynomial

For a fixed graph, the number of proper colorings depends on how many colors are available. With more colors, there are more assignments, but adjacent vertices are still required to receive different colors. The chromatic polynomial packages these counts into one algebraic expression: substituting any positive integer for its variable gives the number of proper colorings using that many labeled colors.

Throughout, graphs are finite and simple: they have no loops or multiple edges. A proper coloring with $q$ labeled colors is a function from the vertex set $V$ to $\{1,2,\dots,q\}$ that assigns different colors to the endpoints of every edge. Colors are labeled, so exchanging two color names generally gives a different coloring. The graph’s chromatic number $\chi(G)$ is the least number of colors needed for a proper coloring; here we count colorings for any positive integer $q$, not just the minimum.

Definition: For a graph $G$ and a positive integer $q$, let $P_G(q)$ be the number of proper colorings of $G$ with $q$ labeled colors. A polynomial $P_G(x)$ that gives these counts, so that $P_G(q)$ is the coloring count for every positive integer $q$, is the chromatic polynomial of $G$.

To see why the coloring count is a polynomial, start with all assignments of colors to vertices, then correct for assignments that give the same color to the endpoints of an edge. The correction must account for overlaps: one coloring can violate several edge constraints at once. Inclusion–exclusion handles these overlaps exactly.

Counting Assignments That Violate Edge Constraints

For a subset $F\subseteq E(G)$, consider the spanning subgraph $(V,F)$, which has all the vertices of $G$ and only the edges in $F$. Let $c(F)$ be its number of connected components, counting isolated vertices as components. If $V$ is empty, set $c(\varnothing)=0$. The following observation identifies the number of assignments that violate every constraint in $F$.

Lemma: For a positive integer $q$, the number of color assignments that give equal colors to the endpoints of every edge in $F$ is $q^{c(F)}$.

Proof. If the endpoints of every edge in $F$ have equal colors, then all vertices in any one connected component of $(V,F)$ must have the same color: along a path, equality at each edge forces equality from its first vertex to its last. Conversely, assigning one color to each component makes the endpoints of every edge in $F$ equal in color. There are $q$ independent choices for each component, so there are $q^{c(F)}$ assignments. If $V$ is empty, there is exactly one assignment, the empty function, and $q^0=1$, as required. $\square$

Theorem: For every finite simple graph $G=(V,E)$ and every positive integer $q$, $$ P_G(q)=\sum_{F\subseteq E}(-1)^{|F|}q^{c(F)}. $$ Consequently, the coloring count is given by a polynomial in $q$.

Proof. Consider all assignments of $q$ colors to $V$. For each edge $e$, let $A_e$ be the set of assignments that give its endpoints the same color. An assignment is proper exactly when it belongs to none of the sets $A_e$. For a fixed assignment, suppose it belongs to $r$ of these sets. Its total contribution to the inclusion–exclusion sum over subsets $F\subseteq E$ is $$ \sum_{F\subseteq \{e:\,\text{the assignment belongs to }A_e\}}(-1)^{|F|} =(1-1)^r. $$ This is $1$ if $r=0$, and $0$ if $r>0$. Thus summing these contributions over all assignments counts precisely the proper ones. For each $F$, the assignments in $\bigcap_{e\in F}A_e$ give equal colors across every edge of $F$, so the Lemma says there are $q^{c(F)}$ of them; for $F=\varnothing$, this is the total of $q^{|V|}$ assignments. Therefore inclusion–exclusion gives the displayed formula. Its right-hand side is a finite sum of integer powers of $q$ with integer coefficients, hence a polynomial. $\square$

For the polynomial itself, replace the integer $q$ in the formula by an indeterminate $x$: $$ P_G(x)=\sum_{F\subseteq E}(-1)^{|F|}x^{c(F)}. $$ The definition’s counting interpretation is asserted for positive integer substitutions. The formula also specifies the polynomial algebraically, including at other values of $x$, without claiming that those values count colorings.

Worked Edge-List Examples

Worked Example: A Path on Three Vertices

Let $G=(V,E)$ have $V=\{1,2,3\}$ and $E=\{12,23\}$. Choose a color for vertex $1$ in $q$ ways. Vertex $2$ must differ from vertex $1$, giving $q-1$ choices. Vertex $3$ must differ from vertex $2$, also giving $q-1$ choices; it may equal vertex $1$. Therefore $$ P_G(q)=q(q-1)^2=q^3-2q^2+q. $$

Check the same result using the theorem. The empty edge subset contributes $q^3$. Each of the two one-edge subsets has two components and contributes $-q^2$, for a combined contribution of $-2q^2$. The subset containing both edges has one component and contributes $q$. Their sum is $q^3-2q^2+q$.

Check: At $q=4$, direct counting gives $4\cdot3\cdot3=36$. Substitution in the polynomial gives $4^3-2\cdot4^2+4=64-32+4=36$.

Worked Example: A Triangle

Let $G=(V,E)$ have $V=\{1,2,3\}$ and $E=\{12,23,13\}$. Choose the color of vertex $1$ in $q$ ways; vertex $2$ then has $q-1$ choices. Vertex $3$ is adjacent to both, whose colors differ, so it has $q-2$ choices. Hence $$ P_G(q)=q(q-1)(q-2)=q^3-3q^2+2q. $$

For an inclusion–exclusion check, the empty edge subset contributes $q^3$. The three one-edge subsets contribute $-3q^2$ in total. Each of the three two-edge subsets makes the three vertices connected, so together they contribute $3q$. The three-edge subset also has one component, but its sign is negative, so it contributes $-q$. Adding gives $q^3-3q^2+3q-q=q^3-3q^2+2q$.

Check: At $q=4$, the direct count is $4\cdot3\cdot2=24$. The expanded polynomial gives $4^3-3\cdot4^2+2\cdot4=64-48+8=24$.

Worked Example: A Triangle with a Pendant Edge

Let $G=(V,E)$ have $V=\{1,2,3,4\}$ and $E=\{12,23,13,14\}$. Vertices $1,2,3$ form a triangle. They can be colored in $q(q-1)(q-2)$ ways, as in the previous calculation. Vertex $4$ is adjacent only to vertex $1$, so it has $q-1$ choices. Thus $$ P_G(q)=q(q-1)^2(q-2). $$

To verify this using the edge-subset formula, first choose a subset $A$ of the three triangle edges, and then decide whether edge $14$ is included. If $A$ has $j$ edges, its subgraph on $\{1,2,3\}$ has $3,2,1,1$ components when $j=0,1,2,3$, respectively. There are $1,3,3,1$ choices of $A$ for those four sizes. Vertex $4$ is initially isolated; including $14$ joins it to the component containing $1$, reducing the component count by one. For each $A$, the two choices about $14$ therefore contribute $(-1)^{|A|}(q-1)q^{c_T(A)}$, where $c_T(A)$ is the component count on the triangle vertices. Summing gives $$ (q-1)(q^3-3q^2+3q-q) =(q-1)(q^3-3q^2+2q) =q(q-1)^2(q-2). $$

Check: At $q=4$, direct counting gives $4\cdot3\cdot2\cdot3=72$. The grouped edge-subset sum gives $3(64-48+12-4)=3\cdot24=72$.

A Common Inclusion–Exclusion Error

For the triangle, a tempting but incorrect calculation is $q^3-3q^2+3q$: it starts with all assignments, subtracts the three single-edge violations, and adds back the three pairwise intersections. It stops there. But an assignment in which all three vertices have the same color belongs to all three edge-violation events. It has been counted once in each pairwise intersection, so the triple intersection must then be subtracted once. There are $q$ such assignments. The correction is $$ q^3-3q^2+3q-q=q^3-3q^2+2q. $$ For $q=4$, the incorrect expression gives $64-48+12=28$, whereas the correct count is $24$. The missing term is not optional: overlapping violations must be accounted for at every subset size.

The edge-subset formula is useful because it turns a coloring problem into a systematic count of equality constraints. For small graphs, direct choices can be quicker; the formula provides a second method for checking the result and explains why the count is polynomial. In either method, keeping colors labeled and enforcing every edge constraint avoids two common sources of error: treating color names as interchangeable, or checking only some of the edges.

Check Your Understanding

Use the definition and the edge-subset formula to answer each question.

For $V=\{1,2,3,4\}$ and $E=\{12,23,34\}$, count proper colorings by choosing vertex colors in order, then expand the result as a polynomial.
For a graph with $V=\{1,2,3\}$ and $E=\{12\}$, how many components does $(V,F)$ have for each subset $F\subseteq E$? Use this to find its chromatic polynomial.
Explain why $q^{c(F)}$, rather than $q^{|F|}$, counts assignments that give equal colors along every edge in $F$.
In the triangle calculation, what is the size of the intersection of all three edge-violation events for a positive integer $q$? Why is its sign negative in inclusion–exclusion?
Why does the polynomial formula count the empty assignment as one when $V=\varnothing$?

From Proper Colorings to Chromatic Polynomials

What You'll Learn