Solving 3-Colouring via 2SAT

摘要

The 3-Colouring of a graph is a classic NP-complete problem. We show that some solutions for the 3-Colouring can be built in polynomial time based on the number of basic cycles existing in the graph. For this, we design a reduction from proper 3-Colouring of a graph G to a 2-CF Boolean formula F_G, where the number of clauses in Fa depends on the number of basic cycles in G. Any model of Fa provides a proper 3-Colouring of G. Thus, Fa is a logical pattern whose models codify proper 3-Colouring of the graph G.