ZykovColor는 Zykov 트리를 모방한 인코딩을 기반으로 그래프 컬러링 문제를 해결하는 새로운 SAT 기반 알고리즘입니다. Hebrard와 Katsirelos (2020)의 접근 방식을 기반으로 전이성 제약 조건을 적용하는 전파기, 탐색 트리 가지치기를 위한 하한 경계, 유추된 전파를 사용합니다. CaDiCal의 최근에 도입된 IPASIR-UP 인터페이스를 활용하여 이러한 기술을 SAT 솔버로 구현합니다. 정점 지배 힌트를 사용하여 통합된 의사 결정 전략을 수정하고, 이전 호출에서 학습된 절을 재사용할 수 있는 증분 하향식 탐색을 사용하는 등 기존 SAT 솔버를 활용한 새로운 기능을 제안합니다. 탐색 중 하한 경계를 개선하기 위해 보다 효율적인 클리크 계산을 통합합니다. 실험 분석을 통해 각 새로운 기능의 효과를 검증합니다. ZykovColor는 DIMACS 벤치마크 집합에서 다른 최첨단 그래프 컬러링 구현보다 성능이 뛰어납니다. 무작위 Erd\H{o}s-Renyi 그래프에 대한 추가 실험은 새로운 접근 방식이 매우 드문 그래프와 고밀도 그래프 모두에서 최첨단 SAT 기반 방법보다 우수함을 보여줍니다.
