Skip to Main content Skip to Navigation
New interface
Conference papers

Clause Learning and New Bounds for Graph Coloring

Abstract : Graph coloring is a major component of numerous allocation and scheduling problems. We introduce a hybrid CP/SAT approach to graph coloring based on exploring Zykov's tree: for two non-neighbors, either they take a different color and there might as well be an edge between them, or they take the same color and we might as well merge them. Branching on whether two neighbors get the same color yields a symmetry-free tree with complete graphs as leaves, which correspond to colorings of the original graph. We introduce a new lower bound for this problem based on Mycielskian graphs; a method to produce a clausal explanation of this bound for use in a CDCL algorithm; and a branching heuristic emulating Brelaz on the Zykov tree. The combination of these techniques in both a branch-and-bound and in a bottom-up search outperforms Dsatur and other SAT-based approaches on standard benchmarks both for finding upper bounds and for proving lower bounds.
Document type :
Conference papers
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Emmanuel Hebrard Connect in order to contact the contributor
Submitted on : Thursday, September 13, 2018 - 12:42:08 PM
Last modification on : Tuesday, October 25, 2022 - 11:58:11 AM
Long-term archiving on: : Friday, December 14, 2018 - 2:37:17 PM


Files produced by the author(s)


  • HAL Id : hal-01873500, version 1


Emmanuel Hébrard, George Katsirelos. Clause Learning and New Bounds for Graph Coloring. International Conference on Principles and Practice of Constraint Programming (CP 2018), Aug 2018, Lille, France. 17p. ⟨hal-01873500⟩



Record views


Files downloads