Map Coloring Possible Colors

JCW2
JCW2 used Ask the Experts™
on
I'm a student and don't expect immediate answers. I need to understand the algorithm that goes with this problem.

6.1) How many solutions are there for the map-coloring problem in Figure 6.1? How many solutions if four colors are allowed? Two colors?
figure.png
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
6.1) How many solutions are there for the map-coloring problem in Figure 6.1? How many solutions if four colors are allowed? Two colors?

what do you think is the answer when 2 colors are allowed?

Author

Commented:
Apparently for this scenario there are no solutions as all of the states besides Tasmania have at least two neighbors, resulting in neighbors with the same color if you go ahead with two.

What about four colors?
ozo
Most Valuable Expert 2014
Top Expert 2015
Commented:
http://en.wikipedia.org/wiki/Chromatic_polynomial
note that map 3-colorability is NP-Complete

Author

Commented:
Thank you for your help.

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial