Roots and Basic Constraints on Chromatic Polynomials

What a Chromatic Root Tells Us

The chromatic polynomial \(P_G(q)\) counts proper vertex colorings when \(q\) is a positive integer, and is treated as a polynomial when \(q\) is allowed to be complex. Its roots encode constraints on coloring, but not every root is an integer or even real. A few basic facts can be read directly from the graph: the number of connected components controls the root at zero, and the presence of an edge determines whether one is a root.

Throughout, graphs are finite and simple. A proper coloring assigns colors to vertices so that adjacent vertices have different colors. The chromatic number \(\chi(G)\) is the least number of colors in a proper coloring of a nonempty graph. We use \(P_G(q)\) for the chromatic polynomial, including for \(q=0\) and complex \(q\), where it means polynomial evaluation rather than a count of colorings with a non-integer number of colors.

For a graph with no vertices, the empty coloring is the unique coloring for every positive integer number of colors, so \(P_G(q)=1\). This case matters: the empty graph has no root at zero. For any nonempty graph, an isolated vertex is still a component and still contributes a factor of \(q\).

The Root at Zero

Write \(c(G)\) for the number of connected components, counting isolated vertices. The polynomial of a disjoint union is the product of the component polynomials: colorings on distinct components can be chosen independently. Consequently, if the connected components are \(H_1,\dots,H_c\), then \(P_G(q)=\prod_{i=1}^c P_{H_i}(q)\). We now establish that each nonempty connected component contributes exactly one factor of \(q\), not a higher power.

Proof. First consider a connected graph \(H\) with \(n\ge1\) vertices. We show that the coefficient \(a(H)\) of \(q\) in \(P_H(q)\) is nonzero. In fact, it has sign \((-1)^{n-1}\). We use induction on the number of edges, with the one-vertex graph as the base case: its polynomial is \(q\), so \(a(H)=1\).

For a connected graph with at least one edge \(e\), deletion-contraction gives \(P_H=P_{H-e}-P_{H/e}\). If \(e\) is not a bridge, \(H-e\) remains connected. The induction hypothesis gives coefficients of \(q\) with signs \((-1)^{n-1}\) in \(P_{H-e}\) and \((-1)^{n-2}\) in \(P_{H/e}\), since contraction has \(n-1\) vertices. Thus subtracting the second coefficient adds positive magnitudes with sign \((-1)^{n-1}\), so \(a(H)\ne0\).

If \(e\) is a bridge, \(H-e\) has two nonempty connected components. Each component polynomial is divisible by \(q\), so their product \(P_{H-e}\) is divisible by \(q^2\) and has coefficient of \(q\) equal to zero. The graph \(H/e\) is connected with \(n-1\) vertices. Hence \(a(H)=-a(H/e)\), which is nonzero and has sign \((-1)^{n-1}\). This completes the induction. Since a connected graph has \(P_H(0)=0\), while its coefficient of \(q\) is nonzero, it has exactly one factor of \(q\). Multiplying the component polynomials gives exactly \(c(G)\) such factors. For the empty graph the polynomial is \(1\), as stated. \(\square\)

In this proof, contraction can produce parallel edges; parallel edges impose the same coloring restriction as a single edge, so they do not change the chromatic polynomial. This is the deletion-contraction convention used here.

When Is One a Root?

Proof. If \(G\) has an edge, a coloring with one color assigns the same color to both endpoints, so it is not proper. There are no proper one-colorings, and \(P_G(1)=0\). If \(G\) has no edges, every assignment of one color to all vertices is proper, and there is exactly one such assignment. Thus \(P_G(1)=1\), including for the empty graph, whose polynomial is also \(1\). Therefore \(P_G(1)=0\) exactly when \(G\) has an edge. \(\square\)

This identifies whether one is a root, but it does not say that the root at one always has the same multiplicity. For example, a graph with an edge need not have a factor \((q-1)^2\); the polynomial itself must be examined to determine multiplicity.

Integer and Nonreal Roots

For a nonempty graph, every integer \(r\) with \(1\le r<\chi(G)\) is a root: no proper coloring with \(r\) colors exists, so \(P_G(r)=0\). Also, zero is a root, with the multiplicity established above. These facts force certain integer roots, but they do not imply that all roots are real. Since a chromatic polynomial has real coefficients, any nonreal root must be accompanied by its complex conjugate.

Proof. Write the polynomial as \(P_G(q)=\sum_{j=0}^n a_jq^j\), where each coefficient \(a_j\) is real. Complex conjugation respects sums and products, so \(P_G(\overline z)=\sum_{j=0}^n a_j\overline z^{\,j}=\overline{\sum_{j=0}^n a_jz^j}=\overline{P_G(z)}\). If \(P_G(z)=0\), then \(P_G(\overline z)=\overline0=0\). \(\square\)

Common Pitfalls and How to Read the Roots

Confusing zero multiplicity with the number of vertices. In the first example there are six vertices but three components, so the zero has multiplicity three, not six. The correct count includes each connected component once, including isolated vertices.

Assuming all roots are real. The cycle examples show why this fails: \(C_4\) and \(C_5\) each have nonreal roots, and those roots occur in conjugate pairs. A real-coefficient polynomial guarantees conjugate pairing, not real roots.

Treating a polynomial evaluation as a coloring count for every input. At positive integer inputs the polynomial counts proper colorings. At a complex input, such as \(1+i\), it is an algebraic evaluation, not a count. In particular, the root at \(1+i\) in the \(C_5\) example does not describe a coloring with a non-integer number of colors.

These basic constraints are useful checks when computing a chromatic polynomial. For a nonempty graph, its factor at zero should reflect its components; an edge forces a root at one; and a nonreal root should have a conjugate partner. They do not determine every root, but they provide reliable tests for a proposed polynomial and help distinguish structural information from numerical coincidence.