Let C=[C1|⋯|Cn] be an m × n matrix with non-zero columns over ℤp. Then the chromatic polynomial of C is defined by
PC(λ) = ΣA(-1)|A|λrank(C)−rank(A),
PC(λ) has the form
PC(λ) = λr − ar −1λr −1 + ⋯ + (−1)ra0,
The flow polynomial of C is defined by
FC(λ) = ΣA(-1)n−|A|λ|A| − rank
FC(λ) = λs − bs −1λs −1 + ⋯ + (−1)sb0,
These polynomials generalize two well-known polynomials associated with a graph:
FG(λ) = ΣA(-1)n−|A|λ|A| − rank(A),
(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.
Last modified 16th September 2013
Return to main page