Home / Computer science / 3-coloring (3COL)
Check
… that Or gadget implements the 3-way disjunction
\begin{equation*} \ell_1 \lor \ell_2 \lor \ell_3. \end{equation*}The Or gadget:
\begin{tikzpicture}[thick]
\usetikzlibrary{fit}
\usetikzlibrary{patterns}
% Styles
\tikzstyle{vertex} = [draw, circle, minimum size = 4ex]
%%%%%%%%%%%%%%%%%
%%% OR GADGET %%%
%%%%%%%%%%%%%%%%%
% Nodes
\node[vertex] (or 1 1) {$c_1$};
\node[vertex, below of = or 1 1, node distance = 6ex] (or 1 2) {$c_2$};
\node[vertex, below of = or 1 2, node distance = 6ex] (or 1 3) {$c_3$};
\node[vertex, right of = or 1 1, node distance = 6ex] (or 1 4) {$c_4$};
\node[vertex, right of = or 1 3, node distance = 6ex] (or 1 5) {$c_5$};
% Edges
\draw (or 1 4) -- (or 1 2) -- (or 1 1) -- (or 1 4) -- (or 1 5) -- (or 1 3);
% Group
\node[draw, dotted,
fit = (or 1 1) (or 1 2) (or 1 3) (or 1 4) (or 1 5),
label = {$y = \ell_1 \lor \ell_2 \lor \ell_3$}
];
%%%%%%%%%%%%%%
%%% INPUTS %%%
%%%%%%%%%%%%%%
% Nodes
\node[vertex, left of = or 1 1, node distance = 8ex] (in 1) {$\ell_1$};
\node[vertex, left of = or 1 2, node distance = 8ex] (in 2) {$\ell_2$};
\node[vertex, left of = or 1 3, node distance = 8ex] (in 3) {$\ell_3$};
% Edges
\draw (or 1 1) -- (in 1);
\draw (or 1 2) -- (in 2);
\draw (or 1 3) -- (in 3);
%%%%%%%%%%%%%%
%%% OUTPUT %%%
%%%%%%%%%%%%%%
% Nodes
\node[
vertex,
below of = or 1 5,
node distance = 8ex,
xshift = -3ex,
pattern=north east lines
] (1) {1};
\node[
vertex,
left of = 1,
node distance = 6ex,
pattern=north east lines
] (0) {0};
\node[
vertex,
below of = 0,
node distance = 6ex,
xshift = 3ex,
pattern=north east lines
] (2) {2};
% Edges
\draw (0) -- (1) -- (2) -- (0);
\draw (or 1 3) -- (1) -- (or 1 5);
% Group
\node[draw, dashed, fit = (1), label = {right: $y = 1$}];
\end{tikzpicture}
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 |