Alternating Signs of Chromatic Polynomial Coefficients

The Sign Pattern

A chromatic polynomial records the number of proper colorings as a function of the number of available colors. Its coefficients need not all be positive, but their signs follow a predictable pattern: starting from the highest power, the signs alternate. The graph’s order matters in stating the rule, and zero coefficients are allowed. We will prove the rule using deletion–contraction and then check it on several explicit graphs.

Throughout, graphs are finite and simple unless stated otherwise. A proper coloring assigns colors to vertices so that adjacent vertices receive different colors. For a graph $G$, its chromatic polynomial $P_G(q)$ is the polynomial whose value at each positive integer $q$ is the number of proper colorings using $q$ available colors. Write $n=|V(G)|$ for the order of $G$.

Theorem: If $G$ is a loopless graph of order $n$, write $P_G(q)=\sum_{k=0}^{n}a_kq^k$, allowing coefficients $a_k=0$. Then, for every $k$ with $0\le k\le n$, $$ (-1)^{n-k}a_k\ge 0. $$ Thus the permitted signs from $q^n$ down to the constant term are $+,-,+,-,\ldots$, with zero coefficients permitted.

The condition is weak rather than strict: it says a coefficient has the indicated sign or is zero. It does not say that every coefficient is nonzero. The theorem also concerns loopless graphs; a graph with a loop has no proper coloring and has zero chromatic polynomial, which is not covered by the stated alternating-sign rule.

Deletion–Contraction and the Induction Step

For an edge $e=uv$, $G-e$ is the graph obtained by deleting $e$. The contraction $G/e$ identifies $u$ and $v$ as one vertex and removes $e$. If this creates parallel edges, discard all but one copy of each edge; call the resulting simple graph $H$. This simplification does not change proper colorings: parallel edges impose the same requirement that their endpoints receive different colors. Since $G$ is simple, contracting $e$ creates no loops. The graph $H$ has order $n-1$.

Deletion–contraction identity: For a loopless simple graph $G$ and an edge $e$, $$ P_G(q)=P_{G-e}(q)-P_H(q), $$ where $H$ is the simplified graph obtained by contracting $e$.

Proof. Fix a positive integer $q$. Among the proper colorings of $G-e$, those giving $u$ and $v$ different colors are exactly the proper colorings of $G$, since the only additional condition in $G$ is that the endpoints of $e$ differ. The remaining colorings of $G-e$ give $u$ and $v$ the same color. Identifying those two vertices gives a proper coloring of $H$, and every proper coloring of $H$ gives exactly one such coloring of $G-e$. Therefore the number of colorings of $G-e$ is the sum of the numbers of colorings of $G$ and $H$. Rearranging proves the identity at every positive integer $q$. Both sides are polynomials, and polynomials agreeing at infinitely many values are identical, so the identity holds as a polynomial identity. $\square$

Proof of the Alternating-Sign Rule

Proof. We use induction on $n+m$, where $n=|V(G)|$ and $m=|E(G)|$, among loopless simple graphs. If $G$ has no edges, then every assignment of colors is proper, so $P_G(q)=q^n$. Its coefficient of $q^n$ is $1$, which satisfies $(-1)^{n-n}1=1$, and all its other coefficients are zero. This also includes the order-zero graph, whose polynomial is $1$.

Now suppose $G$ has an edge $e$, and assume the theorem holds for graphs with smaller order-plus-size. The graph $G-e$ has order $n$ and size $m-1$, so its order-plus-size is smaller than $n+m$. The simplified contraction $H$ has order $n-1$ and at most $m-1$ edges, so it too has smaller order-plus-size. Write $$ P_{G-e}(q)=\sum_{k=0}^{n}b_kq^k,\qquad P_H(q)=\sum_{k=0}^{n-1}c_kq^k, $$ setting missing coefficients equal to zero. By the induction hypothesis, $$ (-1)^{n-k}b_k\ge0 \quad\text{and}\quad (-1)^{n-1-k}c_k\ge0 $$ for their respective index ranges. The deletion–contraction identity gives $a_k=b_k-c_k$ for $0\le k\le n-1$, and $a_n=b_n$. For $k\le n-1$, $$ (-1)^{n-k}a_k =(-1)^{n-k}b_k+(-1)^{n-k+1}c_k =(-1)^{n-k}b_k+(-1)^{n-1-k}c_k \ge0. $$ For $k=n$, $(-1)^{n-n}a_n=b_n\ge0$ by the induction hypothesis for $G-e$. Thus every coefficient satisfies the required inequality, completing the induction. $\square$

The order change in the contraction term is essential. Its order is $n-1$, so its coefficient of $q^k$ has the sign prescribed by $(-1)^{n-1-k}$, the opposite of the sign prescribed at order $n$. The subtraction in deletion–contraction therefore makes the two contributions agree with the required sign rather than cancel it.

Worked Expansions

Worked Example: The Triangle

Let $G$ have vertex set $V=\{1,2,3\}$ and edge set $E=\{12,23,13\}$. Delete edge $13$. The resulting path has edges $12,23$. Coloring vertex $1$ gives $q$ choices, coloring vertex $2$ gives $q-1$ choices, and coloring vertex $3$ gives $q-1$ choices. Hence $$ P_{G-13}(q)=q(q-1)^2=q^3-2q^2+q. $$ Contracting $13$ identifies $1$ and $3$; the remaining edges both join the identified vertex to $2$. After simplifying the parallel edges, the graph is a single edge, so $$ P_H(q)=q(q-1)=q^2-q. $$ Deletion–contraction now gives $$ P_G(q)=(q^3-2q^2+q)-(q^2-q)=q^3-3q^2+2q. $$ For order $3$, the signs permitted on $q^3,q^2,q,1$ are $+,-,+,-$, and the coefficients $1,-3,2,0$ obey that pattern.

Check: Substituting $q=3$ into the expansion gives $27-27+6=6$. Independently, a proper coloring of the triangle with three colors must give its three vertices distinct colors: there are $3$ choices for vertex $1$, $2$ for vertex $2$, and $1$ for vertex $3$, giving $3\cdot2\cdot1=6$.

Worked Example: The 4-Cycle

Let $G$ have vertex set $V=\{1,2,3,4\}$ and edge set $E=\{12,23,34,14\}$. Deleting $14$ leaves the path $1,2,3,4$, whose successive vertices have $q,q-1,q-1,q-1$ choices. Thus $$ P_{G-14}(q)=q(q-1)^3=q^4-3q^3+3q^2-q. $$ Contracting $14$ identifies $1$ and $4$. The remaining edges become $x2,23,3x$, where $x$ is the identified vertex, so the contraction is a triangle. Its polynomial, computed in the preceding example, is $q^3-3q^2+2q$. Therefore $$ \begin{aligned} P_G(q) &=(q^4-3q^3+3q^2-q)-(q^3-3q^2+2q)\\ &=q^4-4q^3+6q^2-3q. \end{aligned} $$ For order $4$, the permitted signs from highest degree down are $+,-,+,-,+$; the coefficients $1,-4,6,-3,0$ have those signs.

Check: At $q=3$, the expansion gives $81-108+54-9=18$. To count directly, choose the color of vertex $1$ in $3$ ways and vertex $2$ in $2$ ways. Vertex $3$ has $2$ choices: if it matches vertex $1$, vertex $4$ has $2$ choices; if it uses the third color, vertex $4$ has $1$ choice because it must differ from both vertices $1$ and $3$. Thus there are $3\cdot2\cdot(2+1)=18$ colorings.

Worked Example: A Triangle and an Isolated Vertex

Let $G$ have vertex set $V=\{1,2,3,4\}$ and edge set $E=\{12,23,13\}$, so vertex $4$ is isolated. The triangle has polynomial $q^3-3q^2+2q$. The isolated vertex can receive any of the $q$ colors independently, so $$ P_G(q)=q(q^3-3q^2+2q)=q^4-3q^3+2q^2. $$ At order $4$, the coefficient signs are $+,-,+,-,+$ from $q^4$ down to the constant term. The coefficients $1,-3,2,0,0$ obey the rule.

Check: At $q=3$, the polynomial gives $81-81+18=18$. Independently, the triangle has $3\cdot2\cdot1=6$ proper colorings, and the isolated vertex has $3$ choices, giving $6\cdot3=18$.

What the Sign Rule Does—and Does Not—Tell You

The theorem is a necessary structural check on a proposed chromatic polynomial. If a coefficient has the wrong sign for the graph’s order, the polynomial cannot be correct. But a matching sign pattern does not prove that the coefficients’ magnitudes are right. It is useful to check a proposed expansion against deletion–contraction or against a direct coloring count as well.

Common pitfall: treating the sign pattern as a full verification. For the triangle, the incorrect expression $q^3-q^2$ has coefficient $-1$ on $q^2$. That coefficient has the permitted sign for order $3$, so the sign rule alone does not detect the error. But at $q=2$, the expression gives $8-4=4$, whereas a triangle has no proper coloring with two colors: its three pairwise adjacent vertices would need three distinct colors. The deletion–contraction computation also gives $q^3-3q^2+2q$, not $q^3-q^2$. The correct lesson is to use the alternating signs as a diagnostic, not as a replacement for computation.

A second source of errors is to state the pattern without reference to the order. For a graph of order $n$, the sign condition is $(-1)^{n-k}a_k\ge0$ for the coefficient of $q^k$. Thus the leading coefficient has positive permitted sign, but the constant-term sign depends on $n$. Keeping the exponent $n-k$ visible avoids confusing this rule with a fixed sign pattern independent of the graph.

Check Your Understanding

Use the order of the graph when determining the permitted signs, and use deletion–contraction where indicated.

For a graph of order $5$, what sign is permitted for the coefficient of $q^2$?
Let $G$ be a single edge together with one isolated vertex. Find $P_G(q)$ and check its coefficient signs.
In the induction proof, why does the contracted graph contribute with the correct sign after it is subtracted?
For the triangle, explain why the coefficient signs alone do not rule out $q^3-q^2$.
In the 4-cycle example, identify the graph obtained by contracting edge $14$, and explain why simplifying parallel edges preserves its chromatic polynomial.