I was reading these lecture notes and I'm trying to understand how one would formally describe reducing 3-colouring to planar 3-colouring. The link pretty much describes the process but understanding the mathematical formalism is a bit over my head. In short, it seems that every edge crossing is replaced with some new graph. How does this work?


The idea is simple. Given an arbitrary graph embedded in the plane, what might make it non-planar is that edges could cross. By slightly perturbing the planar embedding (where we put the vertices), we can ensure that no more than two edges meet at a point.

The idea is to replace each crossing with a certain planar gadget $W$, which functions as a cloverleaf. The four vertices on the outside of the gadget consist of a horizontal pair $x_1,x_2$ and a vertical pair $v_1,v_2$. The gadget has the property that in any valid 3-coloring $c$, $c(x_1) = c(x_2)$ and $c(v_1) = c(v_2)$, and vice versa, for each choice of $c(x_1) = c(x_2)$ and $c(v_1) = c(v_2)$ there is such a coloring.

How do we use this gadget? Suppose that the graph has exactly one crossing, the edge $(a,b)$ crossing the edge $(r,s)$, we put a copy of the gadget with $x_1 = a$ and $v_1 = r$. The gadget ensures that $c(x_2) = c(a)$ and $c(v_2) = c(r)$, so if we connect $x_2$ to $b$ and $v_2$ to $s$, the new graph is 3-colorable iff the original one is (I encourage you to draw this, consulting the lecture notes). Plus, the crossing has been replaced by the gadget, which is itself planar.

The general case is more complicated but of the same spirit, and you can read about it in the proof. The idea is to replace each crossing with a copy of the gadget; two adjacent crossings on the same edge share vertices, as illustrated on page 124 of the lecture notes.

The difficult part in coming up with this reduction is constructing the gadget. The idea itself is pretty natural, and it is somewhat surprising that it can be made to work.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.