structural:scholar_edition, stylistic:style_transfer, information:highlighting, information:filtering
Properties

For fixed G on n vertices, the chromatic polynomial P (G, x) {\displaystyle P(G,x)} is a monic polynomial of degree exactly n, with integer coefficients.

The chromatic polynomial includes at least as much information about the colorability of G as does the chromatic number. Indeed, the chromatic number is the smallest positive integer that is not a zero of the chromatic polynomial,

The polynomial evaluated at − 1 {\displaystyle -1}, that is P (G, − 1) {\displaystyle P(G,-1)}, yields (− 1) | V (G) | {\displaystyle (-1)^{|V(G)|}} times the number of acyclic orientations of G.

The derivative evaluated at 1, P ′ (G, 1) {\displaystyle P'(G,1)} equals the chromatic invariant θ (G) {\displaystyle \theta (G)} up to sign.

If G has n vertices and c components G 1, …, G c {\displaystyle G_{1},\ldots,G_{c}}, then

We prove this via induction on the number of edges on a simple graph G with n {\displaystyle n} vertices and k {\displaystyle k} edges. When k = 0 {\displaystyle k=0}, G is an empty graph. Hence per definition P (G, x) = x n {\displaystyle P(G,x)=x^{n}}. So the coefficient of x n − 1 {\displaystyle x^{n-1}} is 0 {\displaystyle 0}, which implies the statement is true for an empty graph. When k = 1 {\displaystyle k=1}, as in G has just a single edge, P (G, x) = x n − x n − 1 {\displaystyle P(G,x)=x^{n}-x^{n-1}}. Thus coefficient of x n − 1 {\displaystyle x^{n-1}} is − 1 = − | E (G) | {\displaystyle -1=-|E(G)|}. So the statement holds for k = 1. Using strong induction assume the statement is true for k = 0, 1, 2, …, (k − 1) {\displaystyle k=0,1,2,\ldots,(k-1)}. Let G have k {\displaystyle k} edges. By the contraction-deletion principle,

P (G, x) = P (G − e, x) − P (G / e, x), {\displaystyle P(G,x)=P(G-e,x)-P(G/e,x),}

Let P (G − e, x) = x n − a n − 1 x n − 1 + a n − 2 x n − 2 − ⋯, {\displaystyle P(G-e,x)=x^{n}-a_{n-1}x^{n-1}+a_{n-2}x^{n-2}-\cdots,} and P (G / e, x) = x n − 1 − b n − 2 x n − 2 + b n − 3 x n − 3 − ⋯. {\displaystyle P(G/e,x)=x^{n-1}-b_{n-2}x^{n-2}+b_{n-3}x^{n-3}-\cdots.} Hence P (G, x) = x n − (a n − 1 + 1) x n − 1 + ⋯ {\displaystyle P(G,x)=x^{n}-(a_{n-1}+1)x^{n-1}+\cdots }. Since G − e {\displaystyle G-e} is obtained from G by removal of just one edge e, a n − 1 = k − 1 {\displaystyle a_{n-1}=k-1}, so a n − 1 + 1 = k {\displaystyle a_{n-1}+1=k} and thus the statement is true for k.

The last property is generalized by the fact that if G is a k -clique-sum of G 1 {\displaystyle G_{1}} and G 2 {\displaystyle G_{2}} (i.e., a graph obtained by gluing the two at a clique on k vertices), then

A graph G with n vertices is a tree if and only if