The discussion at http://mathoverflow.net/questions/31577 got me thinking about specific promises on a graph that would reduce the complexity of the coloring problem from NP-complete to some (presumably) tighter class; in particular, are there any classes of graphs $G$ for which the 3-coloring question (can a given $g \in G$ be 3-colored?) is reducible to Graph Isomorphism? This seems like the natural intermediate complexity class for the problem, but at least a quick web survey didn't show any related results.
Editing to make the question more concrete: To try and maintain some non-triviality, is there some 'reasonably definable' set of graphs $G$ such that three-colorability of graphs in $G$ is equivalent (mutually reducible) to GI? My first inclination was to define 'reasonable' as 'first-order with quantifiers ranging over individual graphs' (and of course, edge and vertex quantifiers 'within' those graphs, presumably even second-order quantifiers over sets of verts and edges), but from doing some web scouring it's not even clear that many nice and even relevant properties like planarity are so defineable. (Although being 3-colorable itself is, of course: ∃V0,V1,V2(∀v∈V0∀w∈V0(〈v,w〉∉E), etc.) ) I'm thinking of equivalence in terms of mutual oracularity; given an oracle for GI we can decide (in polynomial time) for any given graph $g\in G$ whether $g$ is 3-colorable, and contrariwise given an oracle that decides 3-colorability for any graph $g\in G$ we can decide in polynomial time any instance of GI.