The Last Unsolved Four-Colored Rectangle-Free Grid: The Solution ofExtremely Complex Multiple-Valued Problems
Bernd Steinbach and Christian Posthoff
Graph coloring is a basic method to find optimal solutions in a wide field of applications. It is a multiple-valued problem in case of more than two colors. The colors can be assigned to the vertices or the edges of the graph.
We solve in this paper the last unsolved coloring problem for rectangle-free bipartite graphs using four colors. This special bipartite graph can be represented by the grid G12,21 of 12 rows and 21 columns where all grid positions must be colored by one of four colors. The condition for the solution is that the four cross-points of any pair of rows and any pair of columns are not colored by the same color. Due to the fixed size of the grid and the fixed number of four colors, it is a finite problem. However, the number of color patterns is equal to 412∗21 = 5.2374 ∗ 10151. Hence, we are going to solve an extremely complex multiple-valued problem. A very deep analysis and the smart utilization of the found properties allow us to solve this last unsolved four-colored rectangle-free grid.
Keywords: Four-valued coloring, rectangle-free grid, Boolean equation, SATsolver, Latin square, permutation class.