4 ms·
>The only grid that we do not know if it is 4-colorable is 12x21. This is still open and you are URGED to work on it. Is this a typo for 21x21? If not, then p
by endtime 15y ago
>The only grid that we do not know if it is 4-colorable is 12x21. This is still open and you are URGED to work on it.
Is this a typo for 21x21? If not, then presumably 21x21 is known to be 4-colorable...and it seem to me that removing a column from the edge* of a 4-colored grid results in another 4-colored grid (since the resulting subgrid couldn't have contained any MRs if the original grid didn't)...so a 12x21 4-colored grid should result from removing nine columns from a 21x21 such grid.
I don't actually think the above solves the problem - rather, I must be misunderstanding it. Can someone explain how?
*The column doesn't have to be from the edge, but it's a sufficient claim, and is easier to see...I couldn't be bothered to write the small proof that removing a column from the middle works.
- jbri 15y agoIt's also possible to mathematically prove that certain grids are not 4-colorable.
- endtime 15y agoAh, thank you. And also, duh.
- panic 15y agoYour argument only works if the 21x21 grid is known to be 4-colorable. But in fact, the 21x21 grid is known not to be 4-colorable.
- deleted 15y ago[deleted]