{"id":32560,"date":"2026-01-21T17:02:12","date_gmt":"2026-01-21T17:02:12","guid":{"rendered":"https:\/\/lamarr-institute.org\/publication\/sat-encoding-of-partial-ordering-models-for-graph-coloring-problems\/"},"modified":"2026-06-08T13:21:00","modified_gmt":"2026-06-08T13:21:00","slug":"sat-encoding-of-partial-ordering-models-for-graph-coloring-problems","status":"publish","type":"publication","link":"https:\/\/lamarr-institute.org\/de\/publication\/sat-encoding-of-partial-ordering-models-for-graph-coloring-problems\/","title":{"rendered":"SAT Encoding of Partial Ordering Models for Graph Coloring Problems"},"content":{"rendered":"<p>In this paper, we revisit SAT encodings of the partial-ordering based ILP model for the graph coloring problem (GCP) and suggest a generalization for the bandwidth coloring problem (BCP). The GCP asks for the minimum number of colors that can be assigned to the vertices of a given graph such that each two adjacent vertices get different colors. The BCP is a generalization, where each edge has a weight that enforces a minimal &#8222;distance&#8220; between the assigned colors, and the goal is to minimize the &#8222;largest&#8220; color used.<\/p>\n<p>For the widely studied GCP, we experimentally compare the partial-ordering based SAT encoding to the state-of-the-art approaches on the DIMACS benchmark set. Our evaluation confirms that this SAT encoding is effective for sparse graphs and even outperforms the state-of-the-art on some DIMACS instances.<\/p>\n<p>For the BCP, our theoretical analysis shows that the partial-ordering based SAT and ILP formulations have an asymptotically smaller size than that of the classical assignment-based model. Our practical evaluation confirms not only a dominance compared to the assignment-based encodings but also to the state-of-the-art approaches on a set of benchmark instances. Up to our knowledge, we have solved several open instances of the BCP from the literature for the first time.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In this paper, we revisit SAT encodings of the partial-ordering based ILP model for the graph coloring problem (GCP) and suggest a generalization for the bandwidth coloring problem (BCP). The GCP asks for the minimum number of colors that can be assigned to the vertices of a given graph such that each two adjacent vertices get different colors. The BCP is a generalization, where each edge has a weight that [&hellip;]<\/p>\n","protected":false},"author":12,"featured_media":0,"template":"","meta":{"_acf_changed":false,"footnotes":""},"publication-type":[32],"class_list":["post-32560","publication","type-publication","status-publish","hentry","publication-type-inproceedings"],"acf":[],"publishpress_future_workflow_manual_trigger":{"enabledWorkflows":[]},"_links":{"self":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/32560","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication"}],"about":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/types\/publication"}],"author":[{"embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/users\/12"}],"version-history":[{"count":0,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/32560\/revisions"}],"wp:attachment":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media?parent=32560"}],"wp:term":[{"taxonomy":"publication-type","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication-type?post=32560"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}