# Calculating number of legal solutions for map coloring

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

$$T=3^6=729$$

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

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

-