Theorem. PLANAR-3-COLORABILITY ≣ P PLANAR-MAP-3-COLORABILITY.
(A plane three-coloring problem can be mutually regulated with a plane graph three-coloring problem!)
2.Planar 3-colorability is NP-complete
a. First prove that it is an NP problem. It is a good proof as long as we find one of the solutions in polynomial time.
b. We can reduce the 3-colorability problem to the flat 3-colorability problem.
c. Given any 3 coloring instance G, we can construct a plane 3 coloring instance, if this plane can be 3 colored, then G is 2 colorable.
(1) Flat 3 coloring features
If each plane can be colored by 3, then the opposite corners have the same color, and other colors can be deduced in turn.
Lemma. W is a planar graph such that:
・In any 3-coloring of W, opposite corners have the same color.
・Any assignment of colors to the corners in which opposite corners have
the same color extends to a 3-coloring of W.
Pf. The only 3-colorings (modulo permutations) of W are shown below.
Given instance G of 3-COLOR, draw G in plane, letting edges
cross. Form planar Gʹ by replacing each edge crossing with planar gadget W.
Lemma. G is 3-colorable iff Gʹ is 3-colorable.
・In any 3-coloring of W, a ≠ aʹ and b ≠ bʹ.
・If a ≠ aʹ and b ≠ bʹ then can extend to a 3-coloring of W.