
%tseva.tex: Automatic Generation of  Generating Functions for Chromatic Polynomials
%for Grid Graphs (and more general creatures) of fixed (but arbitrary!) width 
%%a Plain TeX file by Shalosh B. Ekhad, Jocelyn Quaintance, and Doron Zeilberger
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{Automatic Generation of  Generating Functions for Chromatic Polynomials}
\centerline
{
for Grid Graphs (and more general creatures) of Fixed (but arbitrary!) Width
}
\rm
\bigskip
\centerline
{By {\it Shalosh B. EKHAD}, {\it Jocelyn QUAINTANCE}, and {\it Doron ZEILBERGER}}

\bigskip
{\qquad  \qquad  \qquad  D\'edi\'e \`a la m\'emoire de PHILLIPPE FLAJOLET (
$1^{er}$ d\'ecembre 1948-22 mars 2011)
\bigskip
\bigskip
\bigskip
One of the {\it many} things done in the famous INRIA {\bf ALGORITHM PROJECT},
the brain child of our beloved guru Phillippe Flajolet,
was to devise efficient algorithms for computing {\it Chromatic polynomials} for {\it grid graphs},
namely the Cartesian product $P_n \times 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)=\sum_{n=0} CP(\P_n \times P_m,c) z^n \quad,
$$
is a {\it rational function} of {\bf both} $c$ and $z$. In  this modest note, we
would like to briefly describe the Maple package {\tt KamaTzviot} that auotomatically
computes these rational function for {\it any} inputed numeric $k$.
This is accomplished by procedure {\tt GFk(k,t,c)}.

In fact we  do something much more general.
For {\it any} graph $G$,  {\tt KamaTzviot} can (explicitly!) compute

$$
F_G(z,c)=\sum_{n=0} CP(\P_n \times G,c) z^n \quad,
$$
This is accomplished by procedure {\tt GFG(G,t,c)};



In fact we  do something {\it even} more general!
For {\it any} graph $G$, on $m$ vertices, and for {\it 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, \dots , 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 \leq 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 \times P_k$.

{\tt KamaTzviot} can (explicitly!) compute
$$
F_{G,C}(z,c)=\sum_{n=0} CP(M_n(G,C),c) z^n \quad,
$$
This is accomplished by procedure {\tt GFGG(G,C,t,c)};




\hrule
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


\end









