Let C=[C_{1}|⋯|C_{n}] be an m × n matrix with non-zero columns over ℤ_{p}. Then the chromatic polynomial of C is defined by

P_{C}(λ) = Σ_{A}(-1)^{|A|}λ^{rank(C)−rank(A)},

P_{C}(λ) has the form

P_{C}(λ) = λ^{r} − a_{r −1}λ^{r −1} + ⋯ + (−1)^{r}a_{0},

The flow polynomial of C is defined by

F_{C}(λ) = Σ_{A}(-1)^{n−|A|}λ^{|A| − rank
(A)}.

F_{C}(λ) = λ^{s} − b_{s −1}λ^{s −1} + ⋯ + (−1)^{s}b_{0},

These polynomials generalize two well-known polynomials associated with a graph:

- the chromatic polynomial P
_{G}(λ) where C = I_{G}is the incidence matrix of the graph. Then P_{G}(λ) = λ^{κ(G)}P_{IG}, where κ(G) is the number of connected components of G. - The flow polynomial F
_{G}(λ) of a graph, where C is a matrix whose rows over ℤ_{2}form a basis for the cycle space of G, i.e., the null space of I_{G}.

AlternativelyF

where A runs over the column submatrices of I_{G}(λ) = Σ_{A}(-1)^{n−|A|}λ^{|A| − rank(A)},_{G}and n is the number of edges of G.

F

F

F

(see *link* for the 2 and 3-colourings).

The algorithm used here is only appropriate for small graphs. For faster and more sophisticated algorithms, the reader should consult references 1 and 6 below.

- Martin H.G. Anthony,
*Computing chromatic polynomials*, Ars Combinatoria 29C (1990) 216-220. - Tamás Hubai,
*The chromatic polynomial*. - B. Jackson,
*Zeros of chromatic and flow polynomials of graphs*, J. Geom., 76, 95-109 (2003). - K.R. Matthews,
*An example from power residues of the critical problem of Crapo and Rota*, J. Number Theory 9 (1977) 203-208. - James Oxley,
*The contributions of Dominic Welsh to matroid theory*. *Code for Computing Tutte Polynomials*, David Pearce.- Ronald C. Read,
*An Introduction to Chromatic Polynomials*, J. Combinatorial Theory 4 (1968) 52-71. - Richard Stanley,
*Log-Concave and Unimodal Sequences in Algebra, Combinatorics and Geometry*. - W.G. Tutte,
*Graph Theory*, CUP 1984. - Vince Vatter,
*Binomial coefficients, unimodality, log-concavity*. - Eric W. Weisstein,
*Chromatic Polynomial*, MathWorld - A Wolfram Web Resource.

Enter the matrix of integers from 0,1,...,p−1, (with nonzero columns) either

(i) as a string of mn integers separated by spaces,

or

(ii) cut and pasted from a text or other file, with entries separated by spaces and each row ended by a newline. See creating the incidence matrix of a graph.

row dimension (2 ≤ m ≤ 15):

column dimension (1 ≤ n ≤ 15):

prime:

Matrix:

*Last modified 16th September 2013*

Return to main page