How to reduce 2-coloring to 2-SAT
If all you require is a polynomial-time reduction, then test in polynomial time if $G$&nbsp;is $2$-colourable. If it is, map it to the formula&nbsp;$X$; if it isn't, map it to $X\land\lnot X$.