A Customized SAT-based Solver for Graph Coloring

Society for Industrial and Applied Mathematics eBooks 2026

View at publisher
Authors: Timo Brand, Daniel Faber, Stephan Held, Petra Mutzel
DOI: 10.1137/1.9781611978957.11
Cited by: 1

Abstract

We introduce ZykovColor, a novel SATbased algorithm to solve the graph coloring problem working on top of an encoding that mimics the Zykov tree. Our method is based on an approach of Hébrard and Katsirelos (2020) that employs a propagator to enforce transitivity constraints, incorporate lower bounds for search tree pruning, and enable inferred propagations.

Fields of Study & Subjects

Advanced Graph Theory Research Constraint Satisfaction and Optimization Complexity and Algorithms in Graphs

Publication details

Journal / source
Society for Industrial and Applied Mathematics eBooks
Publisher
Society for Industrial and Applied Mathematics
Pages
142–155
Publication date
1 January 2026
Language
EN