Rectangle-Free Colorings of Extremely Complex Grids Using 4 Colors
Bernd Steinbach, Christian Posthoff · 2013
The topic of this paper is the rectangle-free coloring of grids using four colors which is equivalent to the edge coloring of complete bipartite graphs without complete monochromatic subgraphs K2,2. Despite a strong mathematical background it is not known whether rectangle-free 4-colorable grids exist for five large grid sizes. We present in this paper an approach that solves the most complex problems, the rectangle-free 4-colorings of grids of the dimensions 17× 17, 17× 18, 18× 17, and 18× 18.