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

Dédié à la mémoire de PHILLIPPE FLAJOLET ( 1^{er} décembre 1948-22 mars 2011)

One of the many things done in the famous INRIA ALGORITHM PROJECT, the brain child of our beloved guru Phillippe Flajolet, was to devise efficient algorithms for computing Chromatic polynomials for grid graphs, namely the Cartesian product P_{n} × P_{m} where P_{n} is the path of length n. It is fairly easy to see that for a fixed m, the generating function

F_{m}(z, c) = ∑_{n=0} CP (P_{n} × P_{m}, c)z^{n} ,

is a rational function of both c and z. In this modest note, we would like to briefly describe the Maple package KamaTzviot that auotomatically computes these rational function for any inputed numeric k. This is accomplished by procedure GFk(k,t,c).

In fact we do something much more general. For any graph G, KamaTzviot can (explicitly!) compute

F_{G}(z, c) = ∑_{n=0} CP (P_{n} × G, c)z^{n} ,

This is accomplished by procedure GFG(G,t,c);

In fact we do something even more general! For any graph G, on m vertices, and for any bi-partite (m, m) graph C, let M_{n}(G, C) be the graph on mk vertices where the edges among

1 + im, 2 + im, ...m + im

mimick the graph G (for i = 0, …, n − 1), and in addition the edges between

1 + im, 2 + im, ...m + im

and

1 + (i + 1)m, 2 + (i + 1)m, ...m + (i + 1)m

(0 ≤ i < n) mimick the edges of C. Note that when C is the monogamy bipartite graph with m men and m women, where Mr i is connected to Mrs i (but no cheating!, one loves someone else’s spouse), then M_{n}(G, C) reduces to the Cartesian product G × P_{k}.

KamaTzviot can (explicitly!) compute

F_{G,C}(z, c) = ∑_{n=0} CP (M_{n}(G, C), c)z^{n} ,

This is accomplished by procedure GFGG(G,C,t,c);

Shalosh B. Ekhad, Department of Mathematics, Rugters University, c/o zeilberg at math dot rutgers dot edu

Jocelyn Quaintance, Department of Mathematics, Rugters University, quaintan at math dot rutgers dot edu

Doron Zeilberger, Department of Mathematics, Rugters University, zeilberg at math dot rutgers dot edu