3-Coloring With Variable and Clause Gadgets

From Boolean Formulas to Graph Colorings

A graph is 3-colorable if its vertices can be assigned three colors so that adjacent vertices receive different colors. The challenge in a reduction from 3-SAT is to make this local edge rule express a global logical condition: every clause must have at least one true literal. We will use a fixed triangle as a palette, a pair of vertices for each Boolean variable, and a clause construction whose colorings encode whether the clause is satisfied.

Throughout, graphs are finite and simple. A proper 3-coloring is a function from the vertex set to a set of three colors such that the endpoints of every edge have different colors. A 3-SAT formula here is a conjunction of clauses, each containing exactly three literal occurrences; repetitions are allowed. A literal is a variable or its negation. The formula is satisfiable if some assignment of true or false to its variables makes every clause true.

The Palette, Variable Gadget and Clause Gadget

For a formula with variables \(x_1,\dots,x_n\) and clauses \(C_1,\dots,C_m\), begin with three vertices \(T,F,B\) joined pairwise. In any proper 3-coloring, these vertices have three different colors. We name the colors by the palette vertices receiving them; a coloring can always be relabeled so that the color of palette vertex \(T\) is called \(T\), and likewise for \(F\) and \(B\).

For each Boolean variable \(u\), including auxiliary variables introduced below, add two vertices \(u\) and \(\bar u\), and the edges \(u\bar u,uB,\bar uB\). Since both vertices are adjacent to \(B\), they can receive only colors \(T\) or \(F\). Since they are adjacent to each other, one receives \(T\) and the other \(F\). We interpret \(u=T\) as the variable being true and \(\bar u\) as its negated literal. Thus the gadget forces the two vertices to represent opposite truth values.

We first describe a small gadget for the condition that three Boolean inputs are not all equal. Given three input vertices \(a,b,c\), each already restricted to colors \(T,F\), add three fresh vertices \(q_1,q_2,q_3\), join them pairwise to form a triangle, and add edges \(q_1a,q_2b,q_3c\). The inputs need not be distinct; the three \(q\)-vertices are always fresh and distinct.

Proof. If all three inputs have color \(T\), each \(q_i\) is forbidden to use \(T\), so the triangle on \(q_1,q_2,q_3\) would have to be colored using only \(F,B\). A triangle needs three different colors, which is impossible. If all inputs have color \(F\), each \(q_i\) is restricted to \(T,B\), which is also impossible. Conversely, suppose the inputs are not all equal. One input color then occurs once and the other occurs twice. If, for example, the inputs are \(T,F,F\), color \(q_1,q_2,q_3\) by \(F,T,B\), respectively. The triangle receives three different colors, and each \(q_i\) differs from its attached input. If the inputs are \(F,T,T\), use \(T,F,B\), respectively. Permuting the positions gives a valid coloring for every ordering of either mixed pattern. Thus a proper extension exists exactly when the inputs are not all equal. \(\square\)

For each clause \(C_j=(\ell_1\vee\ell_2\vee\ell_3)\), introduce a fresh auxiliary Boolean variable \(z_j\) with the same variable gadget. Add two separate three-input gadgets: one with inputs \((\ell_1,\ell_2,z_j)\), and one with inputs \((\bar z_j,\ell_3,F)\). Here \(F\) means the palette vertex of color \(F\). Each occurrence of a literal is represented by its variable vertex or its negation vertex.

Proof. If \(a=b=c=d=A\), where \(A\) is either Boolean value, the first triple can be non-monochromatic only if \(z\) is the value opposite to \(A\). Then \(\bar z=A\), so the second triple is \((A,A,A)\), a contradiction. Conversely, suppose the four values are not all equal. If \(a\ne b\), the first triple is already non-monochromatic for either choice of \(z\). If \(c\ne d\), the second is also non-monochromatic for either choice, so a choice exists. If instead \(c=d=C\), choose \(z=C\); then \(\bar z\ne C\), making the second triple non-monochromatic. Now suppose \(a=b=A\). Since the four values are not all equal, \(c,d\) are not both \(A\). Choose \(z\) opposite to \(A\). The first triple is non-monochromatic, and the second begins with \(\bar z=A\); because \(c,d\) are not both \(A\), that triple is non-monochromatic too. This proves both directions. \(\square\)

Take \(d=F\) in the lemma. The four values \(\ell_1,\ell_2,\ell_3,F\) are not all equal exactly when at least one of \(\ell_1,\ell_2,\ell_3\) is true. Thus the two gadgets, with the auxiliary variable \(z_j\), implement the clause’s logical OR.

The Reduction and Its Correctness

Proof. First suppose the formula has a satisfying assignment. Color the palette with its three named colors, and color each variable pair according to the assignment: a true variable vertex gets \(T\) and its negation vertex gets \(F\), with the colors reversed for a false variable. Every clause has at least one true literal, so the four Boolean inputs \((\ell_1,\ell_2,\ell_3,F)\) are not all equal. By the second lemma, choose a value for \(z_j\) making both associated triples non-monochromatic. Color its variable pair accordingly. By the first lemma, each of the two clause triangles has a proper coloring extending its inputs. The clause gadgets have separate fresh vertices, so these choices do not conflict across clauses. This gives a proper 3-coloring of the entire graph.

Conversely, suppose \(G\) has a proper 3-coloring. The palette triangle uses all three colors; name them \(T,F,B\) according to the palette vertices. Each variable gadget then assigns opposite Boolean colors to its pair, so it defines a consistent truth assignment to the original variables and to each auxiliary variable \(z_j\). By the first lemma, each of the two clause triangles has non-monochromatic inputs. The second lemma therefore implies that \((\ell_1,\ell_2,\ell_3,F)\) is not all equal. Since its last value is \(F\), at least one of the three literals is \(T\). This holds for every clause, so the original formula is satisfied.

For the size bound, the graph has \(3\) palette vertices, \(2(n+m)\) variable vertices (the original variables and one auxiliary variable per clause), and \(6m\) clause-triangle vertices. Hence it has \(3+2n+8m\) vertices. Its edges consist of \(3\) palette edges, \(3(n+m)\) edges in variable gadgets, and \(12m\) edges in clause gadgets: each of the \(2m\) triangles contributes three triangle edges and three input edges. Thus the total is \(3+3n+15m\). All vertices and edges can be listed by scanning the formula and adding a fixed number of objects per variable and clause, so the construction takes polynomial time. \(\square\)

Worked Constructions

Why 3-Coloring Is in NP

A certificate for a 3-coloring is a list assigning one of three color labels to each vertex. A verifier checks that every label is one of the three permitted labels and scans the edge list to check that the endpoints of each edge have different labels. With an ordinary explicit graph encoding, this takes time polynomial in the input length. A graph is 3-colorable exactly when some certificate passes these checks; therefore 3-coloring belongs to NP.

The earlier material on 3-SAT establishes that 3-SAT is NP-complete for the stated clause format. The reduction theorem proves that 3-coloring is NP-hard, and the certificate argument proves that it belongs to NP. Together these facts establish that 3-coloring is NP-complete.

Common Pitfall: A Triangle Alone Does Not Encode OR

A tempting but incorrect clause construction is to make a triangle whose three vertices are each adjacent to one literal. If all three literals are false, each triangle vertex is restricted to \(T,B\), so the triangle cannot be colored. But if all three literals are true, each triangle vertex is restricted to \(F,B\), and the triangle again cannot be colored. That gadget rejects a clause with all true literals as well as one with all false literals, so it does not represent OR. The two-triangle construction avoids this error: it implements a four-input non-monochromatic condition with the final input fixed to \(F\), which fails exactly when all three clause literals are false.