SAT Encoding of Partial Ordering Models for Graph Coloring Problems

Daniel Faber, Adalat Jabrayilov, Petra Mutzel

In this paper, we suggest new SAT encodings of the partial-ordering based ILP model for the graph coloring problem (GCP) and the bandwidth coloring problem (BCP). The GCP asks for…