Enumeration of Colored Tilings on Graphs via Generating Functions

Abstract

In this paper, we study the problem of partitioning a graph into connected and colored components called blocks. Using bivariate generating functions and combinatorial techniques, we determine the expected number of blocks when the vertices of a graph $G$, for $G$ in certain families of graphs, are colored uniformly and independently. Special emphasis is placed on graphs of the form $G\times P_n$, where $P_n$ is the path graph on $n$ vertices. This case serves as a generalization of the problem of enumerating the number of tilings of an $m\times n$ grid using colored polyominoes.