Chromatic polynomial

In the mathematical field of graph theory the chromatic polynomial for a given graph is a polynomial which encodes the number of different ways to vertex color the graph using n colors. It was first used by Birkhoff and Lewis in their attack on the four-color theorem.

It remains an unsolved problem to characterize graphs which have the same chromatic polynomial and to determine precisely what polynomials are chromatic.

Constructing the chromatic polynomial is hard and at least an NP-complete problem.

Definition

Let us denote by <math>f(G, t)<math> the number of different colorings of a labeled graph G from <math>t<math> colors. Two colorings of G will be considered different if at least one of the labeled points is assigned a different color.Then, it can be shown that <math>f(G, t)<math> will be a polynomial in <math>t<math>.

Examples

• The complete graph with 3 vertices (<math>K_3<math>) : <math>f(K_3, t) = t(t-1)(t-2)<math> since the first vertex can be colored in <math>t<math> ways, the second in <math>t-1<math> ways and so on.

• In general, a complete graph <math>K_n<math> with <math>n<math> vertices: <math>f(K_n, t)=\prod_{i=0}^{n-1}(t-i).<math>

• A tree graph <math>T<math> with <math>n<math> vertices : <math>f(T, t)=t(t-1)^{n-1}<math>

• A circle graph <math>C_n<math> with <math>n<math> vertices : <math>f(C_n, t)=(t-1)^n+(-1)^n(t-1)<math>

Properties

• <math>f(G, t) = 0<math>, if <math>t < \chi(G)<math>.
• Let G be a graph with <math>p<math> vertices, <math>q<math> edges, and <math>k<math> components <math>G_1, G_2, ... G_k<math>. Then:
  • <math>f(G, t)<math> has degree <math>p<math>.
  • The coefficient of <math>t^p<math> in <math>f(G, t)<math> is 1.
  • The coefficient of <math>t^{p-1}<math> in <math>f(G,t)<math> is <math>-q<math>.
  • The constant term in <math>f(G, t)<math> is 0.
  • <math>f(G, t) = \Pi_{i=1}^{k} f(G_i, t)<math>.
  • The smallest exponent of <math>t<math> in <math>f(G, t)<math> with a non-zero coefficient is <math>k<math>.
• The coefficients of every chromatic polynomial alternate in signs.
• A graph G with <math>p<math> vertices is a tree if and only <math>f(G, t) = t(t-1)^{p-1}<math>.