Modelling the 3-Coloring of Serial-Parallel Graphs Via Incremental Satisfiability

Abstract

A novel algorithm is presented for the 3-coloring on parallel-serial graphs. Our proposal is based on the logical specifications (using conjunctive normal forms) of the constraints for a valid 3-coloring of a serial-parallel graph, and afterward, to apply incremental satisfiability in order to build efficiently, a valid 3-coloring. Our proposal builds an initial satisfiable conjunctive formula φ, where SAT(φ) requests an exponential time. However, when new clauses are added to φ, then the colors of the vertices of each serial-parallel component of the input graph are determined in automatic and incremental way. Our procedure is deterministic and it finds a valid 3-coloring. It has a linear-time complexity on the size of the graph. We also show the correctness  of our algorithm.