chromaticPolynomial -- computes chromatic polynomial of a graph

Synopsis

Usage:

chromaticPolynomial G
Inputs:
- G, a graph,
Outputs:
- a ring element, 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

Ways to use chromaticPolynomial :

chromaticPolynomial(Graph)

chromaticPolynomial -- computes chromatic polynomial of a graph

Synopsis

Description

See also

Ways to use chromaticPolynomial :

For the programmer