Chromatic Polynomials of Disconnected Graphs

Why Disconnected Graphs Factor

A proper coloring imposes a restriction only on pairs of adjacent vertices: their colors must differ. If a graph has several connected components, no edge joins vertices in different components. Therefore a coloring can be chosen separately on each component, and the choices can use the same colors. This independence is the reason chromatic polynomials of disconnected graphs multiply.

Throughout, graphs are finite and simple. A proper coloring with $q$ colors is an assignment to each vertex of one of $q$ available colors such that adjacent vertices receive different colors. The chromatic polynomial $P_G(q)$ is the polynomial whose value at each positive integer $q$ counts the proper colorings of $G$ with a fixed set of $q$ colors. The earlier material on chromatic polynomials establishes that this counting function is indeed a polynomial.

Definition: A connected component of $G$ is a maximal connected subgraph of $G$. Isolated vertices are components of order one. Write the components as $G_1,\dots,G_c$, where $c$ is the number of components. The graph with no vertices has $c=0$.

The components partition the vertex set, and no edge has endpoints in two different components. A disjoint union means a graph formed from graphs on disjoint vertex sets with no edges added between those sets. Thus every graph is the disjoint union of its components.

The Component Product Rule

Theorem: If $G$ has connected components $G_1,\dots,G_c$, then $$ P_G(q)=\prod_{i=1}^{c}P_{G_i}(q). $$ For the graph with no vertices, the product is the empty product $1$.

Proof. Fix a positive integer $q$, and let the available colors be the fixed set $\{1,\dots,q\}$. Restricting a proper coloring of $G$ to each component gives one proper coloring of each $G_i$. Conversely, choose one proper coloring of every component and combine those assignments on their disjoint vertex sets. The combined assignment is proper: any edge of $G$ lies within one component, where the chosen coloring is proper. These two operations undo each other, so they give a bijection between proper colorings of $G$ and tuples consisting of one proper coloring of each component. The number of such tuples is the product of the numbers of choices for the components. Therefore the two sides of the stated equation have equal values for every positive integer $q$.

It remains to pass from equality of values to equality of polynomials. A nonzero polynomial of degree $d$ has at most $d$ distinct roots: by polynomial division, if $a$ is a root then the polynomial has a factor $x-a$, and induction on the degree bounds the number of its other roots by $d-1$. The difference between the two polynomials in the theorem vanishes at every positive integer, so it cannot be a nonzero polynomial. Hence the polynomials are identical. If $G$ has no vertices, it has exactly one coloring—the empty assignment—for every positive $q$, and its chromatic polynomial is $1$, in agreement with the empty product. $\square$

The product is over components, not over vertices or edges. In particular, an isolated vertex contributes its own factor. The factors count choices of colors from the same palette: they do not require different components to use disjoint sets of colors.

Edgeless Graphs

Corollary: If $G$ is an edgeless graph on $c$ vertices, then $$ P_G(q)=q^c. $$ This includes the graph with no vertices, for which $c=0$ and $P_G(q)=q^0=1$.

Proof. For a positive integer $q$, every vertex can receive any of the $q$ colors, because there are no edges imposing restrictions. The choices at the $c$ vertices are independent, so there are $q^c$ assignments. When $c=0$, there is one assignment to the empty vertex set, and $q^0=1$. Thus the coloring count agrees with $q^c$ for every positive integer $q$; by the polynomial root argument in the theorem, the chromatic polynomial is $q^c$. $\square$

This formula is also consistent with the component product rule. Each vertex of an edgeless graph is an isolated component, and a single isolated vertex has $q$ possible colors, so $c$ such components contribute $q\cdot q\cdots q=q^c$. When $c=0$, there are no factors to multiply and the product is $1$.

Worked Example: An Edgeless Graph

Let $G=(V,E)$ have $V=\{a,b,c,d\}$ and $E=\varnothing$. Each of its four vertices is an isolated component, so the edgeless-graph formula gives $$ P_G(q)=q^4. $$

For a direct count with three colors, each of $a,b,c,d$ has three choices and there are no restrictions between their choices. Thus the count is $3\cdot3\cdot3\cdot3=81$. Substituting $q=3$ into the polynomial gives $3^4=81$, the same count.

Check: all four vertices may receive the same color, because no two vertices are adjacent. There are $4$ vertices, so the degree of $q^4$ also matches the number of independent color choices when $q$ is positive.

Calculating with Components

To use the product rule on a particular graph, first identify every component, including any isolated vertices. Then calculate the polynomial of each component and multiply the factors. A component polynomial can be counted directly by assigning colors in an order that exposes the restrictions. The calculations below use only these direct counts and the component product rule.

Worked Example: A Triangle, an Edge, and Two Isolated Vertices

Let $G=(V,E)$, where $V=\{1,2,3,4,5,6,7\}$ and $E=\{12,23,31,45\}$. Its components are the triangle on $\{1,2,3\}$, the edge on $\{4,5\}$, and the isolated vertices $6$ and $7$.

For the triangle, vertex $1$ has $q$ choices. Vertex $2$, adjacent to $1$, then has $q-1$ choices. Vertex $3$ is adjacent to both $1$ and $2$, whose colors differ, so it has $q-2$ choices. Its polynomial is $q(q-1)(q-2)$. The edge component has $q$ choices for vertex $4$ and then $q-1$ for vertex $5$, giving $q(q-1)$. Each isolated vertex contributes $q$.

Multiplying the four component factors gives $$ P_G(q)=q(q-1)(q-2)\,q(q-1)\,q\,q =q^4(q-1)^2(q-2). $$

Check: with four colors, the triangle has $4\cdot(4-1)\cdot(4-2)=4\cdot3\cdot2=24$ colorings. The edge has $4\cdot(4-1)=4\cdot3=12$ colorings, and the isolated vertices have $4\cdot4=16$ assignments. The total is $24\cdot12\cdot16=4608$. Substituting four into the product polynomial gives $4^4(4-1)^2(4-2)=256\cdot9\cdot2=4608$, as required.

Worked Example: A Path, a Separate Edge, and an Isolated Vertex

Let $H=(V,E)$, where $V=\{1,2,3,4,5,6\}$ and $E=\{12,23,45\}$. The components are the path with vertices $1,2,3$, the edge $45$, and the isolated vertex $6$.

Count colorings of the path in the order $1,2,3$. Vertex $1$ has $q$ choices. Vertex $2$ has $q-1$ choices because it is adjacent to $1$. Vertex $3$ is adjacent to $2$, so it has $q-1$ choices after the color of $2$ is fixed. It need not differ from the color of $1$, since $13$ is not an edge. The path therefore contributes $q(q-1)^2$. The separate edge contributes $q(q-1)$, and vertex $6$ contributes $q$. Consequently, $$ P_H(q)=q(q-1)^2\cdot q(q-1)\cdot q =q^3(q-1)^3. $$

Check: with three colors, the path has $3\cdot(3-1)\cdot(3-1)=3\cdot2\cdot2=12$ colorings. The edge has $3\cdot(3-1)=3\cdot2=6$, and vertex $6$ has $3$ choices, giving $12\cdot6\cdot3=216$. The polynomial gives $3^3(3-1)^3=27\cdot8=216$. The path count includes colorings in which vertices $1$ and $3$ share a color; that is permitted because they are not adjacent.

Common Pitfall: Making Components Use Different Colors

Consider the graph $J=(V,E)$ with $V=\{u,v\}$ and $E=\varnothing$. Both vertices are isolated. A wrong calculation is $P_J(q)=q(q-1)$, on the grounds that the second vertex must have a different color from the first. That condition would be required if $uv$ were an edge, but it is not required here. Each vertex has $q$ choices, so the correct calculation is $P_J(q)=q\cdot q=q^2$. With two colors, the wrong expression gives $2\cdot(2-1)=2$, whereas the correct count is $2^2=4$: the four assignments are $(1,1),(1,2),(2,1),(2,2)$.

The same issue can arise when applying the component product rule. The theorem says that choices on components are independent; it does not say that different components must use different colors. Requiring separate palettes would exclude valid colorings and replace a product of component counts with a different, generally incorrect count.

The rule is useful whenever a graph separates into disconnected pieces. A complicated graph may have components whose colorings are easier to count individually, and isolated vertices can be included without changing the restrictions on the other components. When checking a calculation, verify that every vertex belongs to exactly one component, that isolated vertices have not been omitted, and that each factor counts colorings using the same available palette.

Check Your Understanding

For each question, identify the components before calculating or explaining the coloring count.

What is the chromatic polynomial of an edgeless graph on five vertices? Explain how the empty graph fits the same formula.
Let $G$ have vertex set $\{1,2,3,4\}$ and edge set $\{12,23\}$. Identify its components and calculate $P_G(q)$.
Why can colorings of separate components be combined without checking additional edges between them?
A graph consists of two disjoint edges. Is its chromatic polynomial $q^2(q-1)^2$ or $q(q-1)(q-2)(q-3)$? Explain what the factors count.
For a path on three vertices, why does the third vertex have $q-1$, rather than necessarily $q-2$, choices after the first two vertices have been colored?