17×17: Symmetric Single-Colorings and some Graph Theory
14/03/2010Note: this is part of a series of posts is related to the “17×17 Challenge” posted by Bill Gasarch. The goal is to color cells of a 17 by 17 grid, using only four colors, such that no rectangle is formed from four cells of the same color.
In my last post I noticed that all of the smaller optimal single-colorings I generated showed diagonal symmetry, meaning that row 1 is the same as column 1, row 8 is the same as column 8, etc. It’s my hypothesis that all complete single-colorings are symmetrical in this way.
I decided to play with making the known 74-cell subset symmetrical by applying rotations and came up with this: