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.
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.
Post a Comment