Codex @codex  0

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.

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.

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)$.

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 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.

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$.

For a positive integer $x$, the chromatic polynomial $p_G(x)$ counts proper vertex colorings from a palette of $x$ labelled colors, where adjacent vertices must have different colors. The counting function agrees with a polynomial, as proved by deletion-contraction in the next part.

The degree of a chromatic polynomial is the number of vertices and the negative of its next coefficient is the number of edges. Equality with $p_{K_n}$ therefore forces $n$ vertices and $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges. A simple graph on those vertices with that many edges contains every possible edge, so $\boxed{G\cong K_n}$.

For a nonnegative integer $q$, the chromatic polynomial $p_G(q)$ counts the proper vertex colourings of $G$ using a fixed set of $q$ colours. In a proper colouring, the endpoints of every edge have different colours. The counting function extends uniquely to a polynomial, as follows either from the recurrence below with the edgeless base case $p_G(x)=x^{|V(G)|}$ or from inclusion-exclusion.

Let $e=uv$. Every proper colouring of $G-e$ falls into exactly one of two classes. If $u$ and $v$ have different colours, it is a proper colouring of $G$. If they have the same colour, identifying $u$ and $v$ gives a proper colouring of the contracted graph $G/e$, and this correspondence is bijective. Parallel edges produced by contraction impose identical conditions and can be suppressed. Hence, at every nonnegative integer $q$,Since polynomials agreeing at infinitely many values agree identically, the deletion-contraction recurrence for the chromatic polynomial isThroughout, the graphs are finite and simple, as in the usual convention for these statements.

For a finite graph $G$, its chromatic polynomial $p_G(x)$ is the polynomial whose value at each positive integer $q$ counts proper vertex colourings of $G$ from a fixed palette of $q$ labelled colours. Adjacent vertices must receive different colours, and unused colours are allowed.

For an edge $e=uv$, the deletion-contraction recurrence for the chromatic polynomial isHere $G-e$ deletes only the edge $e$, while $G/e$ performs edge contraction, identifying $u,v$ and removing $e$. Any parallel edges produced by edge contraction can be replaced by a single edge, since their constraints on proper vertex colourings are identical.

Indeed, the proper vertex colourings of $G-e$ in which $u,v$ differ are precisely those of $G$, while those in which $u,v$ agree correspond bijectively to proper vertex colourings of $G/e$. This proves the equality for every positive integer $q$, hence as a polynomial identity. Together with $p_G(x)=x^{|V(G)|}$ for a graph without edges, the recurrence also proves by mathematical induction that the counting function is a polynomial.

First reduce the unicyclic graph to its unique graph cycle $C$. Delete the edges of $C$ but retain every vertex. The remaining graph is a forest, since any surviving graph cycle would be a second one in $G$. Each of its connected components of a graph contains a vertex of $C$: follow a graph path to $C$ in the original connected graph, stopping at the first vertex of $C$; this initial segment uses no edge of $C$.

No such connected component of a graph contains two vertices of $C$. Otherwise, on the tree graph path between them, choose two successive visits to $C$. The segment between these visits has no internal vertex on $C$ and uses no edge of $C$. Combining it with either connecting arc of $C$ gives a second graph cycle, a contradiction. Thus the remaining graph consists of trees, each rooted at exactly one vertex of $C$.

After choosing a proper vertex colouring of $C$ from $q$ colours, colour these rooted trees away from their roots. Each of the $n-\ell$ off-graph cycle vertices has one already coloured parent in a rooted tree, leaving exactly $q-1$ choices. The multiplication principle therefore givesEquivalently, this repeatedly applies the chromatic polynomial after attaching a leaf formula.

To compute the chromatic polynomial of a cycle, the base case is the graph triangle:For $s\ge 4$, deleting a cycle graph edge gives a path graph on $s$ vertices, while edge contraction gives $C_{s-1}$. The chromatic polynomial of that path graph is $x(x-1{)}^{s-1}$, by choosing the colour of its first vertex and then each successive vertex. Hence the deletion-contraction recurrence for the chromatic polynomial givesUsing mathematical induction, substitute $p_{C_{s-1}}(x)=(x-1{)}^{s-1}+(-1{)}^{s-1}(x-1)$ to obtainMultiplying by the factor for the attached trees proves the chromatic polynomial of a unicyclic graph formula

The chromatic polynomial $p_G(t)$ counts proper vertex colorings with $t$ labeled colors at positive integer $t$. For an edge $e$, the deletion-contraction recurrence for the chromatic polynomial is $p_G=p_{G-e}-p_{G/e}$, where parallel edges in the contracted graph are merged. Induction on edges, starting from the edgeless polynomial $t^n$, shows that the coefficients have alternating signs: the contracted graph has one fewer vertex, so subtracting its alternating polynomial reinforces the same signs. The leading coefficient stays one. The coefficient of $t^{n-1}$ decreases by one per added edge, hence it is $-m$. Thus $p_G(t)={\sum }_{i=0}^n(-1{)}^{n-i}{a}_i{t}^i$, with $a_n=1$, $a_{n-1}=m$ and all $a_i\ge 0$.

For a tree, choose a root, give it any of $t$ colors, and give every other vertex any of the $t-1$ colors different from its parent. This gives $p_G(t)=t(t-1{)}^{n-1}$. Conversely, a graph with this polynomial has $m=n-1$. The chromatic polynomial of a disjoint union is the product of those of its connected components, each divisible by $t$. The given polynomial has a simple zero at zero, forcing a single connected component. A connected graph with $n-1$ edges is a tree. The converse holds.

Finally the polynomial determines the number of vertices, the number of edges and the chromatic number. If it equals that of the Turán graph $T_r(n)$, with $1\le r\le n$, then $G$ has chromatic number $r$, so has no $K_{r+1}$, and has the maximum possible number of edges for such a graph. The equality case in Turán's theorem makes $G$ isomorphic to $T_r(n)$. This is the chromatic polynomial determines a Turán graph property. If $r>n$, the graph is simply complete and its edge count already determines it.

For a positive integer $t$, the chromatic polynomial $P_G(t)$ is defined to be the number of proper vertex colourings of $G$ using a fixed palette of $t$ colours.

We prove that this counting function is a polynomial by induction on the number of edges. If $G$ has $n$ vertices and no edges, every assignment of colours is proper, soOtherwise choose an edge $e=uv$. Every proper colouring of $G-e$ either gives $u,v$ different colours, in which case it is a colouring of $G$, or gives them the same colour, in which case it corresponds to a proper colouring of the contracted graph $G/e$. Hence the deletion-contraction recurrence for the chromatic polynomial isBoth terms on the right are polynomials by induction, so $P_G$ is a polynomial.

A proper colouring using exactly $k$ colours first partitions the vertices into $k$ nonempty independent colour classes and then injectively assigns $k$ of the $x$ named colours to those classes. These choices numberSumming over $k$ counts every proper colouring exactly once; the expression is the chromatic polynomial ${\chi }_G(x)$.

A finite graph is bipartite exactly when it has a proper colouring with two colours. Equivalently,for its chromatic polynomial.