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

Printable View

• Mar 23rd 2012, 11:11 PM
swordfish774
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

http://mathhelpforum.com/image/png;b...AASUVORK5CYII=
• Mar 24th 2012, 02:17 PM
emakarov
Re: Coloring regions in a closed aread such that no adjacent regions have same color
If we label the regions as follows:

Attachment 23428

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.
• Mar 24th 2012, 06:27 PM
swordfish774
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.
• Mar 24th 2012, 07:56 PM
emakarov
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...