2 papers
cs.DM2025
A Customized SAT-based Solver for Graph Coloring
Timo Brand, Daniel Faber, Stephan Held +1
We introduce ZykovColor, a novel SAT-based algorithm to solve the graph coloring problem working on top of an encoding that mimics the Zykov tree. Our method is based on an approac…
math.CO2024
Fractional Chromatic Numbers from Exact Decision Diagrams
Timo Brand, Stephan Held
Recently, Van Hoeve proposed an algorithm for graph coloring based on an integer flow formulation on decision diagrams for stable sets. We prove that the solution to the linear flo…