A Gadget for 3-Colorings

Following up on Bill's post earlier this week on counting the number of 3-colorings, Steven Noble emailed us with some updated information. The first proof that counting 3-colorings is #P-complete is in a 1986 paper by Nati Linial. That proof uses a Turing reduction using polynomials based on posets.

Steven points to a 1994 thesis of James Annan under the direction of Dominic Welsh at Oxford that gives the gadget construction that I so tried and failed to do in Bill's post.

Think of color 0 as false and color 1 as true and use this gadget in place of the OR-gadgets in the regular NP-complete proof of 3-coloring. I checked all eight values of a, b and c and the gadget works as promised.

James Annan later became a climate scientist and co-founded Blue Skies Research in the UK. 

Steven also noted that counting 2-colorings is easy, because for each connected component, there are either 0 or 2 colorings.

Update 4/22/24: We later learned of another gadget construction by Graham Farr in a 1994 Acta Informatica paper.