Transfer-Matrix Methods meet Ehrhart Theory

Counting (proper) colorings of graphs is a classical problem in combinatorics with connections to many different fields. In this talk, we want to examine proper $k$-colorings of graphs of the form $G \times P_n$, where $G$ is any graph, and where $P_n$ is the path graph on $n$ nodes. There are two special cases, namely (1) where $k$ is fixed but not $n$, and (2) where $n$ is fixed but not $k$. In (1), the number of colorings can be determined using the transfer-matrix method, and in (2), the number of colorings can be counted using the chromatic polynomial/Ehrhart theory. We will use the symmetry of $G \times P_n$ to combine the two methods to get explicit formulas (depending on $k$ and $n$) counting the number of colorings and we will give a restricted version of the famous reciprocity theorem for the chromatic polynomial. Furthermore, we will describe the doubly asymptotic behavior of graphs $G \times C_n$, where $C_n$ is the cycle graph with $n$ nodes as both $n$ and $k$ go to infinity. This is joint work with Alexander Engström.