Recognizing 3-colorings cycle-patterns on graphs

We present some patterns based on the basic cycles of a graph for determining proper 3-colorings of graphs. Such patterns are codified by models of a two conjunctive form.Thus, the problem of searching for proper 3-colorings of a graph G   is reduced to determining the satisfiability of a two conjunctive form FGFG (problem denoted as 2-SAT), and where any model of FGFG codifies a way of 3-coloring G.The number of clauses, denoted as the size of FGFG, depends on the number of basic cycles in G  . And as 2-SAT is solvable in polynomial time on the size of FGFG then our algorithm determines some 3-colorings of G in polynomial time on the number of basic cycles of the input graph.

► We present some patterns based on the basic cycles of a graph for determining efficient 3-colorings on graphs.
► We have designed an appropriate combinatorial pattern representing proper 3-colorings of a graph.
► Searching proper 3-colorings of a graph is reduced to build satisfiable assignments of two conjunctive formulas.