# chromaticPolynomial -- computes chromatic polynomial of a graph

## Synopsis

• Usage:
chromaticPolynomial G
• Inputs:
• G, an instance of the type Graph,
• Outputs:
• , the chromatic polynomial of G

## Description

The chromatic polynomial is an invariant of a graph that counts the number of vertex colorings. The value of this polynomial at a natural number n is the number of ways to color the vertices of G using at most n colors, such that no adjacent vertices have the same color.

This method computes the chromatic polynomial as a multiple of the characteristic polynomial of the graphic matroid. Indeed, if M = M(G) is the graphic matroid corresponding to a graph G, then the chromatic polynomial of G equals the characteristic polynomial of M times x^k, where k is the number of connected components of G (which is distinct from the number of components of M).

 i1 : factor chromaticPolynomial cycleGraph 7 2 2 o1 = (x)(x - 2)(x - 1)(x - 3x + 3)(x - x + 1) o1 : Expression of class Product i2 : factor characteristicPolynomial matroid cycleGraph 7 2 2 o2 = (x - 2)(x - 1)(x - 3x + 3)(x - x + 1) o2 : Expression of class Product

The Four Color Theorem states that if G is a planar graph, then its chromatic polynomial has value > 0 at n = 4. In accordance with this, we see that K5 is not planar (on the other hand, note that K_{3,3} is bipartite, hence 2-colorable):

 i3 : factor chromaticPolynomial completeGraph 5 o3 = (x)(x - 4)(x - 3)(x - 2)(x - 1) o3 : Expression of class Product