\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf Frank Simon, Peter Tittmann and Martin Trinks}
%
%
\medskip
\noindent
%
%
{\bf Counting Connected Set Partitions of Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
Let $G=(V,E)$ be a simple undirected graph with $n$ vertices then a
set partition $\pi=\{V_1, \ldots, V_k\}$ of the vertex set of $G$ is a
connected set partition if each subgraph $G[V_j]$ induced by the
blocks $V_j$ of $\pi$ is connected for $1\le j\le k$. Define
$q_{i}(G)$ as the number of connected set partitions in $G$ with $i$
blocks. The partition polynomial is $Q(G, x)=\sum_{i=0}^n
q_{i}(G)x^i$. This paper presents a splitting approach to the
partition polynomial on a separating vertex set $X$ in $G$ and
summarizes some properties of the bond lattice. Furthermore the
bivariate partition polynomial $Q(G,x,y)=\sum_{i=1}^n \sum_{j=1}^m
q_{ij}(G)x^iy^j$ is briefly discussed, where $q_{ij}(G)$ counts the
number of connected set partitions with $i$ blocks and $j$ intra block
edges. Finally the complexity for the bivariate partition polynomial
is proven to be $\sharp P$-hard.
\end{document}