Chromatic polynomial ($P_G(t)$)

The chromatic polynomial turns a graph coloring problem into a counting problem: how many choices remain when adjacent vertices must have different colours? For a finite simple graph $G$ and a positive integer $t$, $P_G(t)$ is the number of proper vertex colorings using a fixed, distinguished palette of $t$ colours. A colouring need not use every available colour, and exchanging two palette colours generally gives a different colouring. Although $P_G$ is a polynomial, its values at arbitrary noninteger arguments are not counts of colourings.

Consider the three-vertex path graph $A$--$B$--$C$. Choose $A$ in $t$ ways, then $B$ in $t-1$ ways, then $C$ in $t-1$ ways: $A$ and $C$ may agree because they are not adjacent. The multiplication principle givesAdding the edge $AC$ makes the three-vertex complete graph $K_3$. Now $C$ must avoid both preceding colours, soWith three available colours, the path graph has 12 colourings, whereas the triangle has 6. With two colours the counts are $2$ and $0$: the extra constraint makes the triangle impossible to colour.

For a nonempty graph, the chromatic number records only the first positive integer $t$ for which $P_G(t)>0$. The chromatic polynomial also counts the choices for every larger palette. For the path the chromatic number is $2$, and for the triangle it is $3$. Counting assignments also gives a useful interpretation for scheduling: if adjacent vertices represent tasks that must use different slots, the chromatic polynomial counts the valid assignments to $t$ named slots. Adding a conflict edge can only remove assignments.

The chromatic polynomial also remembers some of the graph's structure. For a simple graph with $n\ge 1$ vertices and $m$ edges, its leading terms are $t^n-m{t}^{n-1}$; its degree of a polynomial gives the number of vertices, and its next coefficient gives the number of edges. It does not determine the graph completely. A four-vertex path graph and a four-vertex star graph are not related by a graph isomorphism, but both are trees and have chromatic polynomial $t(t-1{)}^3$.

The early connection to map colouring appears in George D. Birkhoff's article ^[ref]. For a derivation of the counting recurrence and its leading coefficients, see Paul Johnson's MAS 341 lecture on chromatic polynomials.

If a unicyclic graph has $n$ vertices and its unique graph cycle has length $\ell$, each of its $n-\ell$ off-graph cycle vertices contributes a factor $x-1$ after its parent in a rooted tree is coloured. Thus $p_G(x)=(x-1{)}^{n-\ell }{p}_{C_{\ell }}(x)$. Substituting the chromatic polynomial of a cycle yields the displayed formula, equivalently by repeated application of the chromatic polynomial after attaching a leaf.

For a cycle graph of length $\ell \ge 3$, the chromatic polynomial is $p_{C_{\ell }}(x)=(x-1{)}^{\ell }+(-1{)}^{\ell }(x-1)$. The graph triangle gives the base case $x(x-1)(x-2)$. For $\ell \ge 4$, the deletion-contraction recurrence for the chromatic polynomial gives $p_{C_{\ell }}(x)=x(x-1{)}^{\ell -1}-p_{C_{\ell -1}}(x)$, since deleting an edge leaves a path graph and contracting it gives the shorter cycle graph. Substitution proves the formula by mathematical induction.

For a finite simple graph on $n$ vertices with $m$ edges and no graph cycle shorter than $\ell$, the coefficient of $x^{n-i}$ in its chromatic polynomial is $(-1{)}^i(\genfrac{}{}{0ex}{}{m}{i})$ for $0\le i\le \min (n,\ell -2)$. In the chromatic polynomial inclusion-exclusion formula, an edge subset containing a graph cycle of length at least $\ell$ has $n-c(F)\ge \ell -1$. Thus every contribution to $x^{n-i}$ in this range is a forest, with exactly $i$ edges. Conversely, all $i$-edge subsets are forests, so precisely $\left(\genfrac{}{}{0ex}{}{m}{i}\right)$ terms contribute, each with sign $(-1{)}^i$.

Here $c(F)$ is the number of connected components of a graph in the spanning subgraph $(V(G),F)$, including isolated vertices. Apply the inclusion-exclusion principle to the conditions that the endpoints of an edge have equal colours. Imposing all such conditions for $F$ forces a single colour on each connected component of a graph, yielding $x^{c(F)}$ for positive integer $x$. The equality extends to a polynomial identity.

For connected components of a graph $G_1,\dots ,G_t$ of a finite graph $G$, choices of proper vertex colourings on different connected components of a graph are independent. The multiplication principle gives $p_G(x)={\prod }_j{p}_{G_j}(x)$. Each nonempty factor is divisible by $x$, hence $x^t$ divides the chromatic polynomial. The vanishing constant term follows by mathematical induction from the deletion-contraction recurrence for the chromatic polynomial, starting with $p_H(x)=x^{|V(H)|}$ for a nonempty graph without edges.

If a simple graph has the same chromatic polynomial as the Turán graph $T_r(n)$, it has the same number of vertices and edges, and the same chromatic number $r$. It is therefore $K_{r+1}$-free and attains equality in Turán's theorem. The equality case forces it to be isomorphic to $T_r(n)$.

Deleting an edge removes one colour constraint. Edge contraction describes exactly the newly admitted colourings that violate that constraint. If $e$ joins distinct vertices $u,v$ of a simple graph $G$, write $G-e$ for the graph with that edge deleted and $G/e$ for the graph with $u,v$ identified and $e$ removed. Parallel edges produced by the contraction may be reduced to one edge, since they impose the same condition on a proper vertex coloring. ThenTo see why, divide the proper vertex colorings of $G-e$ into two classes. Those with different colours at $u,v$ are exactly the colourings of $G$. Those with equal colours at $u,v$ correspond one-to-one to colourings of $G/e$: the merged vertex receives their common colour. Subtracting the second class leaves the first.

For the triangle, delete $AC$ to get a three-vertex path graph, or contract $AC$ to get two vertices joined by an edge after removing the redundant parallel edge. Consequently,At $t=3$, this says $6=12-6$. Of the twelve path colourings pictured above, six give $A,C$ the same colour; these are precisely the ones ruled out when we restore $AC$.

This recurrence is useful because it reduces a constrained counting problem to smaller graphs. A graph on $n$ vertices with no edges has $P_G(t)=t^n$, since every vertex chooses its colour independently. Repeated edge deletion and edge contraction reduce to this case and show that the counting function is a polynomial. The same recurrence gives its leading coefficients. The method is conceptually simple, although the number of recursive cases can still grow rapidly.

Attaching a new vertex that is a leaf of a graph multiplies the chromatic polynomial by $t-1$: after colouring the old graph, the new vertex may receive any colour except its neighbour's. Starting with one vertex and repeatedly adding a leaf of a graph constructs any finite tree. Thus a tree with $n\ge 1$ vertices hasIn contrast, every pair of vertices in a complete graph must receive different colours, so the multiplication principle gives the falling factorialFor positive integers $t<n$ this product vanishes, expressing the impossibility of assigning distinct colours to all $n$ vertices.