Evaluations at Zero, One, and Two Colors

Three Evaluations with Different Meanings

The chromatic polynomial \(P_G(q)\) records the number of proper colorings of a graph when \(q\) is a positive integer. Its values at one and two colors therefore have direct coloring interpretations. The value at zero is different: zero is not a positive number of available colors, so \(P_G(0)\) is a polynomial evaluation, not a count of colorings. These three evaluations give quick information about edges, bipartiteness, and connected components.

Throughout, \(G=(V,E)\) is a finite simple graph, and the graph is nonempty in the sense that \(V\ne\varnothing\). A proper coloring with \(q\) colors assigns each vertex one of \(q\) labeled colors so that adjacent vertices receive different colors. The chromatic polynomial is the polynomial whose value at every positive integer \(q\) equals the number of such colorings. A connected component is a maximal connected subgraph; write \(c(G)\) for the number of components.

For a disconnected graph, choices of proper coloring on distinct components are independent. Thus its chromatic polynomial is the product of the chromatic polynomials of its components. We will use this component rule alongside the evaluations below.

The Evaluations

Proof. First, we show that \(q\) divides \(P_G(q)\) for every nonempty graph \(G\). Use induction on the number of edges. If \(G\) has no edges and \(n=|V|\ge1\), each vertex can be assigned any color independently, so \(P_G(q)=q^n\), which is divisible by \(q\).

Now suppose \(G\) has at least one edge \(e\), and assume the claim holds for nonempty simple graphs with fewer edges. The deletion–contraction identity is \(P_G(q)=P_{G-e}(q)-P_{G/e}(q)\), where parallel edges created by contraction are treated as a single edge. The graph \(G-e\) is nonempty and has fewer edges than \(G\). The contracted graph \(G/e\) is also nonempty: contracting an edge identifies two vertices, and since \(G\) has at least two vertices, at least one vertex remains. After suppressing parallel edges, \(G/e\) has fewer edges than \(G\). By induction, both polynomials on the right are divisible by \(q\); their difference is divisible by \(q\) as well. This proves \(P_G(0)=0\).

For \(q=1\), there is exactly one assignment of the single available color to all vertices. If \(E\ne\varnothing\), the endpoints of any edge receive the same color, so this assignment is not proper and \(P_G(1)=0\). If \(E=\varnothing\), the assignment is proper and is the only one, so \(P_G(1)=1\).

For \(q=2\), a proper coloring is exactly a partition of the vertices into two color classes with every edge crossing between them. Such a coloring exists precisely when \(G\) is bipartite. Suppose \(G\) is bipartite. Consider any one of its components and choose a vertex \(r\) in that component. There are two choices for the color of \(r\). Once that choice is made, every other vertex's color is forced: along any path from \(r\), colors must alternate at each edge. Existence of a bipartition ensures that these forced choices are consistent, and connectedness ensures every vertex is reached by a path. Thus each component has exactly two proper 2-colorings. This also holds for an isolated vertex, which has two choices. Choices on distinct components are independent, so there are \(2^{c(G)}\) colorings. If \(G\) is not bipartite, it has no proper 2-coloring, so \(P_G(2)=0\). \(\square\)

The formula at two colors is not merely a test for whether a bipartition exists. When the graph is bipartite, it counts all possible assignments of the two labeled colors: each component can have its two parts colored in either order.

Worked Evaluations

What the Values Tell You—and What They Do Not

For a nonempty graph, \(P_G(0)\) gives no distinction between different graphs: it is always zero. It follows from the polynomial's factor \(q\), not from counting assignments with zero available colors. The empty graph, with no vertices, is an exception under the usual convention: its chromatic polynomial is \(1\), the empty product, so its value at zero is \(1\).

The value \(P_G(1)\) detects whether there is at least one edge. It does not measure how many edges there are: every nonempty edgeless graph has value \(1\), while every graph containing an edge has value \(0\). The value \(P_G(2)\) detects bipartiteness. If it is positive, then the graph is bipartite; if the graph is bipartite, the value additionally records the number of components through \(2^{c(G)}\). For example, a connected bipartite graph has value \(2\), while a bipartite graph with three components has value \(2^3=8\).

Common pitfall: treating a color assignment as automatically proper. For the path on \(V=\{1,2,3\}\), \(E=\{12,23\}\), one might incorrectly say that two colors give \(2^3=8\) assignments and conclude \(P_G(2)=8\). That counts all assignments, including ones where adjacent vertices have the same color. The correction is to choose the color of vertex \(1\) in \(2\) ways; vertex \(2\) is then forced to the other color, and vertex \(3\) is forced to the color of vertex \(1\). There are \(2\cdot1\cdot1=2\) proper colorings, in agreement with \(P_G(q)=q(q-1)^2\) and with \(2^{c(G)}=2^1=2\).