3
This paper by Régis Barbanchon might be of interest. From the abstract:
We prove that the Satisfiability (resp. planar Satisfiability) problem
is parsimoniously P-time reducible to the 3-Colorability (resp. Planar
3-Colorability) problem, that means that the exact number of solutions
is preserved by the reduction, provided that 3-colorings are counted
...
Only top voted, non community-wiki answers of a minimum length are eligible
