I understand that it is computationally hard to count the 4-colorings of a given graph. See answers to
In a given class of planar graphs (will leave choice of class open) is there a known function f(n) that gives a sharp (or not sharp) upper bound on the maximum number of 4-colorings (modulo permutations of the colors, or not) over all graphs of size n (what constitutes size n left open for now)?
Consider the class of planar triangulations (allowing multi-edges). These are maximal planar graphs (for a fixed number of vertices), i.e. any planar graph can be completed to one. Then the maximal number of 4-colorings of a planar triangulation with $n$ vertices is $3\cdot 2^n$.
To see this, first assume that the triangulation no separating triangle. Whitney proved that any planar triangulation with no separating triangle has a Hamiltonian cycle. On either side of the Hamiltonian cycle, one sees a disk with an $n$-cycle on its boundary, and $n-3$ edges in the interior. The number of colorings of such a graph is $3\cdot 2^n$, since you can color a triangle with $4\cdot 3\cdot 2$ colors, and then the remaining $n-3$ vertices each have $2$ colors available working outwards. So this gives an upper bound on the number of colorings. To achieve this upper bound, take two copies of the triangulated disk, and glue them along the boundary by the identity. Then this is a planar triangulation with the same number of $4$-colorings (of course, there will be many multi-edges, so it is far from simplicial). This class of graphs is a natural class to consider, e.g. in the proof of the $4$-color theorem.
If there is a separating triangle, then one may show that the graph has $<3\cdot 2^n$ $4$-colorings by induction. If a triangulation has a separating triangle, then one may break it up into two triangulations, so that the number of $4$-colorings is the product of the number of colorings of each triangulation $/24$, and by induction one sees that the number of 4-colorings is strictly $<3 \cdot 2^n$.
Maybe you'll object to this choice of graphs, e.g. because of multi-edges. If you make no restriction, then obviously the trivial graph on $n$ vertices will be maximal. For connected graphs, trees will be maximal. Other natural classes are trivalent graphs, bipartite graphs, or simplicial triangulations. I'm not sure about the maximal number of colorings for these classes of graphs.
Addendum: Restricting to $3$-connected simplicial triangulations, the growth is still $O(2^n)$. Consider an $n$-cycle, then the number of $3$-colorings is $O(2^n)$. Then cone it off on both sides to get a simplicial triangulation with $O(2^n)$ $4$-colorings. I'm not sure what the optimal constant is though.
This has been studied in the statistical mechanics literature on the antiferromagnetic 4-state Potts model. One place to start reading about recent work from this perspective is the introduction and first few sections of this paper by Salas and Sokal.
One particularly studied family is triangular lattice graphs, which is expected to be an integrable system in some sense of the term.
This structure has led to one result due to Rodney Baxter which I can easily quote here: For graphs with $n$ sites forming a triangular lattice, in the limit of large $n$, the number of 4-colorings is asymptotically $W^n$ where $W=\frac{3\Gamma(1/3)^3}{4\pi^2}\approx 1.46099$.
Jesper Lykke Jacobsen has conjectured formulas for corrections to this due to boundary and corner effects here.
I'm afraid my understanding is not developed enough to write further, but in any case you might write to Alan Sokal or some of the other authors of these papers for their perspective.
For every tree on $n$ vertices, there are exactly $4 \times 3^{n-1}$ $4$-colorings. This follows from the fact that its chromatic polynomial is $t(t-1)^{n-1}$.
(Or by induction since every tree with at least one edge has a "leaf.")
