How to reduce 3COLOR to 3SAT?

Question

We know that 3SAT ≤p 3COLOR(i.e. 3SAT is polynomial time reducible to 3COLOR). Can anyone give a short argument why 3COLOR ≤p 3SAT? And give an actual Cook reduction showing that 3COLOR ≤p 3SAT Please.

Answer 1

the short answer is: since 3SAT is NP-complete, any problem in NP can be p.t. reduced to solving an instance of 3SAT (or showing it is not satisfiable). Hence 3COLOR <=p 3SAT.

For a construction of p.t. reduction of 3COLOR to SAT, you may see section 2 in the following document (the topic is not related to your question):

http://research.microsoft.com/apps/pubs/default.aspx?id=66816