生成関数を用いたグラフ上の着色タイルの列挙

本論文では、グラフを接続された着色成分であるブロックに分割する問題を研究します。二変数生成関数と組合せ的手法を使用して、特定のグラフのファミリーに属するグラフ G の頂点が均一かつ独立に着色された場合の期待されるブロック数を決定します。特に、P n が n 頂点のパスグラフである形式 G × P n のグラフに重点を置きます。このケースは、着色ポリオミノを使用した m × n グリッドのタイルの数を列挙する問題を一般化するものです。