---

Check

… 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