My sense is that there are hard 3-coloring problems in graphs that don't look "random". Certainly the ones I generate have a small number of vertices with very

My sense is that there are hard 3-coloring problems in graphs that don't look "random". Certainly the ones I generate have a small number of vertices with very high degree, and the others are more reasonable. This is why I say that there are potentially things happening with different random models. But you are certainly right on all counts. However, where you say this: .... it's been given "physicist proofs". There's enough evidence that it's unreasonable to not consider it true. There had been a lot of evidence around for quite some time that primality was harder than P (assuming P!=NP), and yet it turns out to be in P, even without PvsNP being settled. I'm suspicious. I still believe that hard instances can be found, and that "most" of them will look as you describe, random-ish with the right parameters, but I'm wary about claiming that most things that look like that will, in turn, be "hard." But I suspect we're in agreement, possibly "violent agreement." ADDED In EDIT: Forgot to say, thanks for the reference.