Automatic Generation of Generating Functions for Chromatic Polynomials
for Grid Graphs (and more general creatures) of Fixed (but arbitrary!) Width
By Shalosh B. Ekhad, Jocelyn Quaintance, and Doron Zeilberger
.pdf
.ps
.tex
(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger)
Written: March 30, 2011.
Dédié à la mémoire de PHILIPPE FLAJOLET (1er décembre 1948 - 22 mars, 2011)
This short article is modest homage to the great guru who coined the terms analytic combinatorics,
and singular combinatorics, and made us almost love analysis.
Important:
This article is accompanied by the Maple package
KamaTzviot, that automatically computes generating functions for infinite
families of graphs of fixed width (see the article).
Sample Input and Output for the Maple package KamaTzviot
-
If you want to see explicit expressions (as rational functions of t and c) for
the formal power series whose coefficient of tn in its Maclaurin
expansion (with respect to t) would give you the chromatic polynoial of the m by n grid
graph (the Cartesian product of a path of m vertices and a path of length n)
for m=1 to m=6, the
the input
gives the output.
-
If you want to see explicit expressions (as rational functions of t and c) for
the formal power series whose coefficient of tn in its Maclaurin
expansion (with respect to t) would give you the chromatic polynoial of the m by n cylinder
graph (the Cartesian product of a cycle of m vertices and a path of length n)
for m=1 to m=6, the
the input
gives the output.
-
If you want to see the first 30 terms of the sequence of chromatic polynomials
the m by n grid graph (the Cartesian product of a path of m vertices and a path of length n)
for n=1 to n=30, and for m=1 to m=6, followed by the integer sequences for the number
of colorings with 2,3,4, and 5 colors, the
the input
gives the output.
-
If you want to see the first 30 terms of the sequence of chromatic polynomials
the m by n cylinder graph (the Cartesian product of a cycle of m vertices and a path of length n)
for n=1 to n=30, and for m=1 to m=6, followed by the integer sequences for the number
of colorings with 2,3,4, and 5 colors, the
the input
gives the output.
-
If you want to see the the chromatic polynomials for the n by n square grid graphs, for
n between 1 and 7, the
the input
gives the output.
-
If you want to see the the generating function for the chrmoatic polynomials
Mn(G,C) (see the article for the definition) where
G is the 5-vertex graph (whose vertices are labeled {1,2,3,4,5})
G:={{1,2},{2,3},{3,4},{4,5},{1,3},{2,4},{3,5}}:
and C is the bipartite graph
C:={[1,1],[2,2],[3,3],[4,4],[5,5],[1,2],[2,1],[2,3],[3,2],[3,4],[4,3],[4,5],[5,4]}:
the input
gives the output.
Added April 7, 2011: Here is an
addendum written by Jocelyn Quaintance.
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page