arXiv:2504.04821v1 Announce Type: cross 摘要：我们提出了ZykovColor，这是一种基于SAT的新型算法，用于解决基于Zykov树编码的图着色问题。该方法基于H\'ebrard和Katsirelos（2020）提出的一种方法，该方法使用一个传播器强制实施传递性约束，引入搜索树剪枝的下界，并允许启发式的传播。我们利用新引入的IPASIR-UP接口来实现这些技术与一个SAT求解器。此外，我们提出了新的功能，这些功能利用了底层的SAT求解器。这些功能包括修改集成的决策策略，利用顶点支配提示，并采用增量的自底向上的搜索方法，该方法可以从之前的调用中重用学到的子句。此外，我们整合了更高效的团计算，以在搜索过程中改善下界。我们通过实验分析验证了每个新功能的有效性。ZykovColor在DIMACS基准测试集上优于其他最先进的图着色实现。在随机Erd\H{o}s-R\'enyi图上的进一步实验表明，我们的新方法在稀疏和稠密图中均优于最先进的基于SAT的方法。