2
$\begingroup$

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

  • 1
    _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.2012-02-26
  • 0
    Correction: It seems that 3-colorability of _planar_ graphs is easier, so there may be a good solution anyway.2012-02-26
  • 0
    @HenningMakholm: Isn't 3-colourability of planar graphs NP-Hard too?2012-02-26
  • 0
    @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.2012-02-26
  • 0
    @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.2012-02-26
  • 0
    @Aryabhata: Well, 1973 is early enough that the terminology may not have been settled yet.2012-02-26
  • 0
    @HenningMakholm: Yep! Hence unfortunate, instead of 'bad' :-)2012-02-26

1 Answers 1