Boolean-pair colouring gadget
ID: boolean-pair-colouring-gadget
Two graph triangles sharing a vertex force their two opposite edges to use the same two colours in a graph colouring with three colours. A palette graph triangle and another graph triangle therefore force the literal pair to have opposite Boolean colours. This gadget is used in a reduction from 3-SAT to the three-colourability problem.
New to topics? Read the docs here!