… as a special case of COL with

exactly three colors.

… 3SAT to 3COL, showing NP-completeness of the latter.

Perform a polynomial-time reduction using the graph below.

- Create the first vertex colored 2.
- Add 0/1 inputs for each variable.
- Add 0/1 output.
- For each clause:
- Add a new
*Or*gadget. - Connect the gadget to the appropriate inputs.
- Connect the gadget the 1 output.

- Add a new

\[\begin{equation*} F = c_1 \land c_2 \land \cdots = (\ell_{11} \lor \ell_{12} \lor \ell_{13}) \land \cdots \end{equation*} \]

The gadgets:

For example,

\[\begin{equation*} (x_1 \lor \lnot x_2 \lor x_2) \land (x_2 \lor \lnot x_3 \lor x_3) \end{equation*} \]

is reduced to:

… that *Or* gadget implements the 3-way disjunction

\[\begin{equation*} \ell_1 \lor \ell_2 \lor \ell_3. \end{equation*} \]

The *Or* gadget:

No coloring exists when *\(\ell_1 = \ell_2 = \ell_3 = 0\)*:

\(\ell_1\) | \(\ell_2\) | \(\ell_3\) | \(c_1\) | \(c_2\) | \(c_3\) | \(c_4\) | \(c_5\) |
---|---|---|---|---|---|---|---|

0 | 0 | 0 | n/a | 1 | 2 | 2 | 0 |

0 | 0 | 0 | n/a | 2 | 2 | 1 | 0 |

0 | 0 | 0 | 1 | n/a | 2 | 2 | 0 |

0 | 0 | 0 | 2 | n/a | 2 | 1 | 0 |

0 | 0 | 0 | 1 | 2 | n/a | 0 | 2 |

0 | 0 | 0 | 2 | 1 | n/a | 0 | 2 |

0 | 0 | 0 | 1 | 2 | 2 | n/a | 0 |

0 | 0 | 0 | 2 | 1 | 2 | n/a | 0 |

0 | 0 | 0 | 1 | 2 | 2 | 0 | n/a |

0 | 0 | 0 | 2 | 1 | 2 | 0 | n/a |

Otherwise, a coloring exists:

\(\ell_1\) | \(\ell_2\) | \(\ell_3\) | \(c_1\) | \(c_2\) | \(c_3\) | \(c_4\) | \(c_5\) |
---|---|---|---|---|---|---|---|

0 | 0 | 1 | 1 | 2 | 0 | 0 | 2 |

0 | 0 | 1 | 2 | 1 | 0 | 0 | 2 |

0 | 1 | 0 | 1 | 0 | 2 | 2 | 0 |

0 | 1 | 0 | 2 | 0 | 2 | 1 | 0 |

0 | 1 | 1 | 2 | 0 | 0 | 1 | 2 |

0 | 1 | 1 | 2 | 0 | 2 | 1 | 0 |

1 | 0 | 0 | 0 | 1 | 2 | 2 | 0 |

1 | 0 | 0 | 0 | 2 | 2 | 1 | 0 |

1 | 0 | 1 | 0 | 2 | 0 | 1 | 2 |

1 | 0 | 1 | 0 | 2 | 2 | 1 | 0 |

1 | 1 | 0 | 0 | 2 | 2 | 1 | 0 |

1 | 1 | 0 | 2 | 0 | 2 | 1 | 0 |

1 | 1 | 1 | 0 | 2 | 0 | 1 | 2 |

1 | 1 | 1 | 0 | 2 | 2 | 1 | 0 |

1 | 1 | 1 | 2 | 0 | 0 | 1 | 2 |

1 | 1 | 1 | 2 | 0 | 2 | 1 | 0 |

© 2024 Rudolf Adamkovič under GNU General Public License version 3.

Made with Emacs and secret alien technologies of yesteryear.