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).
As I recall, it's also hard to find a four-colouring of a given map (unless there's a one- or two-colouring).