2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I suppose instead of "formula" you mean an "algorithm"? $\endgroup$ – dkaeae Nov 30 '18 at 8:56
5
$\begingroup$

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Juho Nov 30 '18 at 16:35
  • $\begingroup$ @Juho Sorry, I just randomly noticed your comment two months after the fact. I think I meant "To the best of my recollection, there is no known polynomial-time algorithm for producing 4-colourings of general planar graphs." My answer already notes that it's NP-complete to determine whether there's a 3-colouring but I don't know even of a polytime algorithm that takes an arbitrary planar graph and outputs a 4-colouring of it (even if it's allowed to use all four colours on a 3-colourable graph, so it doesn't have to detect 3-colourability). $\endgroup$ – David Richerby Feb 3 at 21:32
  • $\begingroup$ No worries :-) So it should be the case that planar 3-coloring is hard, but planar 4-coloring does have efficient algorithms. See e.g., Wikipedia here. $\endgroup$ – Juho Feb 4 at 11:25
  • $\begingroup$ @Juho Well, you learn something new every day/two months. :) Edited into the answer. $\endgroup$ – David Richerby Feb 4 at 12:09
-1
$\begingroup$

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".

$\endgroup$
  • 1
    $\begingroup$ OK, but we can do much better than this: $\Delta(G)$ can be arbitrarily large, even in planar graphs, but all planar graphs have $\chi(G)\leq 4$. $\endgroup$ – David Richerby Feb 4 at 12:12
  • $\begingroup$ Thank you, I didn`t know this fact! I'll change my answer! $\endgroup$ – Emanuele Feb 5 at 14:27

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.