> In simpler words, the conjecture was that you could assume without loss of generality that the 1s would make a chessboard pattern, and this is not true in general. It is however likely that a modified version of the chessboard conjecture is true. In particular
I'm interested in the conjecture that was stated in the post. That one just says "if a k-coloring exists, then a k-coloring in which the 1s form a perfect checkerboard pattern also exists".
That seems like it's enough to allow you to assume without loss of generality that the 1s form a checkerboard pattern. That's still a huge reduction in the search space - you need to consider that the pattern might be shifted, but that only doubles the amount of work you're doing (since there are only two ways to fill in a checkerboard pattern on a grid), while filling in the checkerboard cuts the amount of work you're doing by a factor of 2^k.
Also, it seems like something of an "error" (maybe not! What do we know about aperiodic colorings?) when thinking about checkerboarding to spend time considering graphs that won't tile the plane. The radius-14 diamond can't tile the plane while checkerboarded; a checkerboard pattern will hit more or less than half of the cells in the grid.
I'm interested in the conjecture that was stated in the post. That one just says "if a k-coloring exists, then a k-coloring in which the 1s form a perfect checkerboard pattern also exists".
That seems like it's enough to allow you to assume without loss of generality that the 1s form a checkerboard pattern. That's still a huge reduction in the search space - you need to consider that the pattern might be shifted, but that only doubles the amount of work you're doing (since there are only two ways to fill in a checkerboard pattern on a grid), while filling in the checkerboard cuts the amount of work you're doing by a factor of 2^k.
Also, it seems like something of an "error" (maybe not! What do we know about aperiodic colorings?) when thinking about checkerboarding to spend time considering graphs that won't tile the plane. The radius-14 diamond can't tile the plane while checkerboarded; a checkerboard pattern will hit more or less than half of the cells in the grid.