A Customized SAT-based Solver for Graph Coloring
Timo Brand, Daniel Faber, Stephan Held, Petra Mutzel · Society for Industrial and Applied Mathematics eBooks · 2026
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.