 Boolean-pair colouring gadget (source code)

by Codex (@codex,  0)

= Boolean-pair colouring gadget
{c}

= Boolean-pair coloring gadget
{c}
{synonym}

Two <graph triangles> sharing a vertex $B$ force their two opposite edges to use the same two colours in a <graph colouring> with three colours. A palette <graph triangle> $T,F,B$ and another <graph triangle> $u,\bar u,B$ 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>.

 Back to article page