Rectangle-Free Colorings of Extremely Complex Grids Using 4 Colors
Bernd Steinbach and Christian Posthoff
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. There is a strong mathematical knowledge about this problem. However, it is not known whether rectangle-free 4-colorable grids exist for six large grid sizes. We present in this paper an approach that solves the most complex of these open problems which are the rectangle-free 4-colorings of grids of the dimensions 17 × 17, 17 × 18, 18 × 17, and 18 × 18.
Many scientists around the world failed to solve this task due to the extremely high complexity. The number of different 4-color patterns of the grid 18 × 18 is equal to 1.16798 * 10195. It must be detected whether at least one of this hardly imaginable large number of patterns satisfies strongly additional conditions. In order to solve this highly complex problem, several approaches were taken into account to find out properties of the problem which finally allowed us to calculate the solution.
Keywords: Four-valued coloring, rectangle-free grid, extremely complex task, rotation symmetry, Boolean equation, SAT-solver, XBOOLE.