The packing chromatic number of the infinite square lattice is between 13 and 15

The packing chromatic number of the infinite square lattice is between 13 and 15
复制标题

DOI：
10.1016/j.dam.2017.03.013
复制
发表时间：
2015-10
期刊：
Discret. Appl. Math.
影响因子：
--
通讯作者：
Barnaby Martin;F. Raimondi;Taolue Chen;Jos Martin
Barnaby Martin;F. Raimondi;Taolue Chen;Jos Martin
中科院分区：
其他
文献类型：
--
作者：
Barnaby Martin;F. Raimondi;Taolue Chen;Jos Martin

文献摘要

被引文献

相似文献

利用sat求解器在部分已知解的基础上，将无限方阵的填充色数上界从17提高到15。我们讨论了sat解决这类问题的优点，并比较了不同编码的性能。此外，我们再次使用sat求解器将下界从12提高到13，展示了该技术在我们方法中的多功能性。
Using a SAT-solver on top of a partial previously-known solution we improve the upper bound of the packing chromatic number of the infinite square lattice from 17 to 15. We discuss the merits of SAT-solving for this kind of problem as well as compare the performance of different encodings. Further, we improve the lower bound from 12 to 13 again using a SAT-solver, demonstrating the versatility of this technology for our approach.