Results 1 to 4 of 4

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

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    39

    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

    Attached Thumbnails Attached Thumbnails Coloring regions in a closed aread such that no adjacent regions have same color-44466_001.png  
    Last edited by swordfish774; March 24th 2012 at 03:08 AM. Reason: Missed a statement
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773

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

    If we label the regions as follows:

    Coloring regions in a closed aread such that no adjacent regions have same color-decoded.png

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2010
    Posts
    39

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773

    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...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. contraction regions
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: October 2nd 2011, 01:19 PM
  2. Mathematica - sum of regions
    Posted in the Math Software Forum
    Replies: 0
    Last Post: June 6th 2010, 10:51 AM
  3. Regions in 3D-space
    Posted in the Geometry Forum
    Replies: 1
    Last Post: July 17th 2009, 05:34 AM
  4. Replies: 1
    Last Post: April 23rd 2009, 06:27 AM
  5. Areas of these regions
    Posted in the Calculus Forum
    Replies: 2
    Last Post: February 19th 2009, 04:49 PM

Search Tags


/mathhelpforum @mathhelpforum