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?

  • I suppose instead of "formula" you mean an "algorithm"? – dkaeae Nov 30 at 8:56

No.

  • 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).

  • In your last paragraph, did you mean "a three-colouring of a given map"? It's indeed true as well, i.e., planar 3-coloring is NPC. – Juho Nov 30 at 16:35

In this case the problem is NP-complete. By the way we know that:
$\text{Given a graph }G\text{, let }X_G \text{ be the number of colors of G and } D_G\text{ the maximum number of adjacents in G,}$we have that $X_G\le D_G+1 $

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.