Is there a formula for determining the minimum number of colors to color a map with n counties such that no adjacent county have the same color?
The famous four-colour theorem says that four colours are always enough (assuming that counties are contiguous areas of land).
It's easy to tell if one colour is enough: this is the case only if every county is an island, so has no border with any other county.
It's easy to tell if two colours is enough: this corresponds to the adjacency graph being bipartite. You can determine this by colouring an arbitrary county red, then colouring all its neighbours blue, then colouring all their neighbours red, and so on. If this process produces a legal colouring, you have your colouring; if it fails, it turns out that there is no colouring with two colours.
If two colours isn't enough, then it's NP-complete to tell whether three is enough or you have to use four. This means that, as far as we know, there's no efficent algorithm to determine whether an arbitrary map can be coloured with three colours. This is a result due to Garey, Johnson and Stockmeyer (Some simplified NP-complete graph problems, Theoretical Computer Science, 1(3):237--267, 1976; Science Direct).
There are efficient algorithms to find four-colourings of planar graphs: the two computer-assisted proofs that four colours is enough both gave algorithms. But, as noted above, there's no known efficient algorithm to tell whether four colours is optimal for a given map.
In this case the problem is NP-complete. By the way we know that:
Given a graph $G$, let $\chi(G)$ be the number of colors of $G$ and $\Delta(G)$ the maximum degree in $G$. we have that $\chi(G)\le \Delta(G)+1$.
However if $G$ is a planar graph (a map), then $\chi(G)\le 4$.
For more information see the "Four color theorem by Kenneth Appel and Wolfgang Haken".