A c-coloring of G(n,m)=n x m is a mapping of G(n,m) into {1,...,c} such that no four corners forming a rectangle have the same color. In 2009 a challenge was proposed via the internet to find a 4-coloring of G(17,17). This attracted considerable attention from the popular mathematics community. A coloring was produced; however, finding it proved to be difficult. The question arises: is the problem of grid coloring is difficult in general? We show that the problem of, given a partial coloring of a grid, can it be extended to a full (proper) coloring, is NP-complete.
翻译：G(n,m) =n x m 的 c- 彩色是 G(n,m) 到 {1,..., c} 的映射图, 使成矩形的四角没有相同的颜色。 2009年, 通过互联网提出了一个挑战, 以寻找 G( 17, 17) 的 4 彩色。 这吸引了流行数学界的极大关注 。 制作了彩色, 但是, 发现它很困难 。 问题是: 网格的彩色问题一般是否很困难? 我们显示, 网格部分的彩色问题能否扩大到完整的( 适当的) 彩色问题 。
相关内容
微信扫码咨询专知VIP会员