{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T05:08:21Z","timestamp":1778562501534,"version":"3.51.4"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,8]]},"abstract":"<jats:p>Graph coloring is a major component of numerous allocation and scheduling problems.\nWe introduce a hybrid CP\/SAT approach to graph coloring based on exploring Zykov\u2019s 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.\nWe 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.\nThe combination of these techniques in a branch- and-bound search outperforms Dsatur and other SAT-based approaches on standard benchmarks both for finding upper bounds and for proving lower bounds.<\/jats:p>","DOI":"10.24963\/ijcai.2019\/856","type":"proceedings-article","created":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T03:46:05Z","timestamp":1564285565000},"page":"6166-6170","source":"Crossref","is-referenced-by-count":2,"title":["Clause Learning and New Bounds for Graph Coloring"],"prefix":"10.24963","author":[{"given":"Emmanuel","family":"Hebrard","sequence":"first","affiliation":[{"name":"LAAS-CNRS, Universit\u00e9 de Toulouse, CNRS, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Katsirelos","sequence":"additional","affiliation":[{"name":"UMR MIA-Paris, INRA, AgroParisTech, Universit\u00e9 Paris-Saclay, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"name":"Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}","theme":"Artificial Intelligence","location":"Macao, China","acronym":"IJCAI-2019","number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2019,8,10]]},"end":{"date-parts":[[2019,8,16]]}},"container-title":["Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T03:52:17Z","timestamp":1564285937000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2019\/856"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2019,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2019\/856","relation":{},"subject":[],"published":{"date-parts":[[2019,8]]}}}