I recently met with a professor to discuss this problem and she didn't have an answer for how to do the calculation. What I did learn is that the counting itself is considered NP-Hard and is in a class known as #P. I'm currently running an efficient 4-coloring on a map of the US (contiguous 48) and was hoping to be able to compare the brute force count with a known value.
Any help is appreciated.
Are you familiar with the chromatic polynomial for a graph?
The idea is this: Let $\chi(G)$ be the number of 4-colorings of the graph $G$.
Consider these three graphs:
A.
B.
C.
(Where the two ovals are the same in each case, and might be connected by other edges not shown.)
I claim that $\chi(A) = \chi(B) + \chi(C)$. For in any coloring of $A$, the two indicated vertices might be the same color, or different colors. But any coloring in which the two vertices have the same color can be converted to a coloring of $B$, and vice versa, so these are equinumerous, And any coloring in which the two vertices have different colors can be converted to a coloring of $C$, and vice versa, so these are also equinumerous. So the number of colorings of $A$ is equal to the number of colorings of $B$ plus the number of colorings of $C$.
Inverting this relation, we have $$\chi(C) = \chi(A) - \chi(B)\tag{$\star$}$$ which is useful because both $A$ and $B$ are strictly simpler than $C$: $A$ has one fewer edge than $C$, and $B$ has one fewer edge and one fewer vertex. So we can compute $\chi(C)$ in terms of simpler graphs.
Using these relations we can compute, for any graph $G$, the number of $4$-colorings of $G$.
For example, let's start by observing that $\chi(\bullet) = 4$ and $\chi(\bullet\bullet) = 16$. Now by relation $(\star)$ we have $\chi($
$) = \chi(\bullet\bullet)-\chi(\bullet) = 16-4 = 12.$
Now let's calculate $\chi($
$)$. This is equal to $\chi($
$)-\chi($
$)$ from which we can factor out the $\chi($
$)$ term, obtaining $\chi($
$)\cdot(\chi(\bullet)-1)$. We know that the left term is 12 by the previous computation, and the right term is 3, so the total is $12\cdot 3=36$.
The difficulty here (and there must be one, because the problem is #P-complete) is that each recursion tends to double the number of evaluations of $\chi$ that is required. So a naïve evaluation on the USA state border graph will require $2^{48}$ steps, which is prohibitively expensive.
But the USA graph is of a very special type. It is planar, and is made almost entirely of triangles. (It contains only two primitive 4-cycles, and no primitive cycles of more than 4 vertices.) So one might expect that by choosing the correct recursion order, one could reduce the 48-vertex graph quickly to a strictly smaller and simpler graph.
For example, suppose $G$ is a graph that has a dangling triangle that is not otherwise connected to the graph, as happens in the case of Washington, which borders only Idaho and Oregon, which border one another. One can easily show in this case, using the rules above, that $\chi(G)=2\chi(G')$, where $G'$ is obtained from $G$ by deleting Washington. The reduced $G'$ has only 47 vertices, and might then have another, similar triangle that could be similarly deleted.
I think this could be made to work for this particular example.