next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Matroids :: chromaticPolynomial

chromaticPolynomial -- computes chromatic polynomial of a graph

Synopsis

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.

i1 : factor chromaticPolynomial cycleGraph 7

                        2            2
o1 = (x)(x - 2)(x - 1)(x  - 3x + 3)(x  - x + 1)

o1 : 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 K3,3 is bipartite, hence 2-colorable):

i2 : factor chromaticPolynomial completeGraph 5

o2 = (x)(x - 4)(x - 3)(x - 2)(x - 1)

o2 : Expression of class Product

See also

Ways to use chromaticPolynomial :