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