prove that 3-colorability of planar graphs is NP-hard:
(a) Prove that in any legal 3-coloring of the crossover gadget, the opposite corners are forced to have
the same color.
(b) Prove that any assignment of colors to the corners such that opposite corners have the same color
extends to a legal 3-coloring of the entire crossover gadget.
(c) Use the following idea to prove that 3-colorability of planar graphs is NP-hard: Replace each point
at which another edge crosses edge (u, v) with a copy of the crossover gadget G. For example, replace figure-1 with figure-2
Hi there! Click one of our representatives below and we will get back to you as soon as possible.