Rudy’s OBTF Rudolf Adamkovič

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}
0ceb40bf-4e47-4aee-89db-b404445c4ee1.svg

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

© 2025 Rudolf Adamkovič under GNU General Public License version 3.
Made with Emacs and secret alien technologies of yesteryear.