Suppose a square grid graph $g$ of side length $n$ can be colored with $q$ colors. In how many unique colorizations are no adjacent vertices the same color?
A friend and I have been trying to find a poly time algorithm to solve this, and in our research we stumbled upon the OEIS wiki page which seems to provide the solutions up until the 10-colorization of a $13\times 13$ grid. However, it goes into little depth about how the solutions are calculated, and I profess that I am ignorant to the subject of chromatic polynomials which it cites. Additionally, we are unsure of the applicability of the solutions to our precise problem (e.g. isn't the $q$-colorization of a vertex (case $n=1$) equal to $q$, and not 1?)
Instead, we have attempted find a general solution using more intuitive methods. It is easy to see that for a graph $1\times n$, the number of colorizations without adjacencies using $q$ colors is $q(q-1)^{n-1}$. However, in trying to solve for the square graphs, it becomes more complicated. I hold the belief that this is solvable recursively by solving for the $x\times y$ graphs from $x=1,y=1$ incrementally to $x=n,y=n$, employing the results from the $x\times (y-1)$ and $(x-1)\times y$ graphs. Unfortunately, this solution is getting pretty messy pretty fast. Might there be a simpler way of thinking about this problem?
This isn't an answer to the question, but let me at least indicate an elementary method to solve the corresponding problem for the $2 \times n$ grid, which is to repeatedly use the deletion-contraction recurrence to get a recursive expression in $n$. If $P(G_{m, n})$ denotes the chromatic polynomial of the $m \times n$ grid graph, then if I haven't made a mistake we get
$$P(G_{2, n+1}) = (q^2 - 3q + 3) P(G_{2, n})$$
and hence by induction
$$P(G_{2, n}) = (q^2 - 3q + 3)^{n-1} q (q - 1).$$
For higher $m$ you need to apply deletion-contraction about $2m$ times and it gets messy to organize the work, but for fixed $m$ this should give a pretty straightforward algorithm as a function of $n$.