6 ms·
A related and unsolved question (and thus legitimate) could be: what is the smallest c such that 1000x1000 is c-colorable.
by brent 17y ago
A related and unsolved question (and thus legitimate) could be: what is the smallest c such that 1000x1000 is c-colorable.
- RiderOfGiraffes 17y agoThe problem with that is knowing that you have the minimum. The good thing about the question as asked is that it's asking for something specific and not a proof of impossibility. Your question is legitimate and interesting, but requires a proof of minimality. That's difficult.
- deleted 17y ago[deleted]
- brent 17y ago> That's difficult Agreed, but that is why it would be worth $1M :-).
- klipt 17y agoA different question would be "who can come up with the smallest c in 6 months", which probably wouldn't yield the true answer, but for a $1M prize it might come quite close (and could lead to some interesting theoretical advancements).
- cjg 17y agoAccording to http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17x17chart.pdf http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17x17chart.pdf c would be either 17 or 18.
- cjg 17y agoSorry, misread the parent post.