News for hackers. Stuff that matters.
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by jules on Monday November 30, 2009 @07:44PM (#969021)
So if they say "Exactly one of a,b,c is in OBS4" then one of a,b,c is not 4-colorable?
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by jrp on Monday November 30, 2009 @08:15PM (#969046)
OBS4 is supposed to be a list of all configurations which deny 4-colorability for themselves, and any strictly larger (in both dimensions) configurations.

Ie, if (19,17) is in OBS4 then (19+x,17+y) is not 4-colorable either. So given a shape (x,y) or even a more funky collection of grid points like a triangle, to know if it's 4-colorable just check for all X in OBS4, if you can fit X inside your shape.

Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by jules on Monday November 30, 2009 @08:58PM (#969095)
Got it, although the more interesting property is that smaller shapes than those in OBS are 4-colorable? (because it is trivially true that if nxk cannot be colored then larger shapes can't either).
Re:The 17x17 challenge. "Worth $289.00. This is not a joke." by jrp on Tuesday December 01, 2009 @02:43AM (#969419)
Right, he has apparently solved and proved a short list for OBS3 with the property that X is 3-colorable if and only if X doesn't contain anything from OBS3.