Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a map with six regions that needs to be colored with three colors it is very trivial to find the total number of map colorings including illegal solutions (i.e., two adjacent regions have the same color).


What is an effective method to calculate the total number of legal solutions (i.e., no two adjacement regions have the same color)?

share|cite|improve this question
Effective? Enumerate all of them, counting which of them are legal. Efficient as the number of regions get larger? Unknown, but probably impossible. Finding out even whether the number of legal solutions is zero or not (i.e., recognizing 3-colorable graphs) is an NP-complete problem. – Henning Makholm Feb 26 '12 at 2:49
Correction: It seems that 3-colorability of planar graphs is easier, so there may be a good solution anyway. – Henning Makholm Feb 26 '12 at 3:09
@HenningMakholm: Isn't 3-colourability of planar graphs NP-Hard too? – Aryabhata Feb 26 '12 at 3:13
@Aryabhata: Perhaps I misunderstood the reference I found (Stockmeyer 1973) -- it's beind a paywall and the title only said "polynomial complete", which I took to mean complete for deterministic polynomial time. However, there also seems to be cites to it that describe it as proving NP-hardness. – Henning Makholm Feb 26 '12 at 3:28
@HenningMakholm: That is an unfortunate title. I believe he means non-deterministic polynomial (i.e. NP) complete, as that is the paper which first proved the NP-Completeness of 3-colourability of planar graphs. – Aryabhata Feb 26 '12 at 3:35

It matters how the regions are connected to each other.

You can model your regions as a graph. To compute the number of colouring of a graph with $t$ colours, you can try computing its Chromatic Polynomial $P(t)$, which can be computed recursively, and compute $P(3)$.

For a given graph of $6$ vertices, it should be doable by hand.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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