# Math Help - Coloring regions in a closed aread such that no adjacent regions have same color

1. ## Coloring regions in a closed aread such that no adjacent regions have same color

4 colors available, find the number of ways you can color the regions such that no adjacent regions have same color

2. ## Re: Coloring regions in a closed aread such that no adjacent regions have same color

If we label the regions as follows:

then the dual graph (not counting the exterior region) is shown here. The number of proper colorings is the value of the chromatic polynomial of the graph at 4. This software gives the chromatic polynomial as

$-x ( 3(1-x) + 15(1-x)^2 + 31(1-x)^3 + 34(1-x)^4 + 21(1-x)^5 + 7(1-x)^6 + (1-x)^7 )$

Its value at x = 4 is 576.

3. ## Re: Coloring regions in a closed aread such that no adjacent regions have same color

Check the solution given here. Does the numbering matter? I started from the region you have numbered as 8. Got the answer as 648, I used the approach used in the solution I mentioned above. Have I made any mistake? Can you provide a solution on the lines of the one mentioned on the webpage I linked to, but starting from region 8? Thank you.

4. ## Re: Coloring regions in a closed aread such that no adjacent regions have same color

Yes, with a program for computing chromatic polynomials I went a bit far, didn't I?

There are 4 choices for H and 3 choices for G.

(a) E = F; then there are 2 choices for E = F.
(a1) C = D; then there are 2 choices for C = D, 2 choices for B and 2 for A. Total for (a), (a1): 12 * 2^4.
(a2) C ≠ D; then there are 2 choices for C, 2 for D, 1 for B and 1 for A. Total for (a), (a2): 12 * 2^3.

(b) E ≠ F; then there are 2 choices for E and 2 for F.
(b1) C = D; them there is 1 choice for C, 1 for D, 2 for B and 2 for A. Total for (b), (b1): 12 * 2^4.
(b2) C ≠ D; then there is 1 choice for C, 2 for D, 1 for B and 1 for A. Total for (b), (b2): 12 * 2^3.

Total: 12 * 2 * (2^4 + 2^3) = 576.

Maybe it can be shortened a bit...