2012/05/16 by Daniel Apon, Apon, Daniel, William Gasarch +3
Computer Science · Mathematics · #03F20 #68Q17 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.2.2 #F.4.1 #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1205.3813
openalex publication_date 2012/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.