Take auxiliary graph triangles and , join to , and add edges . When has colour and the inputs have colours in , this graph admits an extension to a graph colouring with three colours exactly when at least one input is . All-false inputs force , contradicting their edge. Conversely, use if , if , and if . The extension property is necessary for both directions of a polynomial-time many-one reduction.
Articles by others on the same topic
There are currently no matching articles.