The discussion at Decision problem restricted to inputs that satisfy some necessary condition. 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.
Best Answer
Hi Steven,
(1) To start with the "duh" observation, you could define an artificial class, namely "those 3-coloring instances that are obtained by starting from Graph Isomorphism and then applying a standard NP-completeness reduction." That would indeed give you a subclass of 3-coloring instances that are provably polynomially equivalent to graph isomorphism, but I'm guessing it's not what you had in mind. :-)
(2) I can't think of a "natural" subclass of 3-coloring instances that are reducible to graph isomorphism and not as a consequence of being in P. I'd be interested and surprised if there was one -- 3-coloring and GI are both about graphs, but in complexity terms they're extremely different! GI has lots of special group-theoretic structure, which in some sense can't be shared by 3-coloring (or any other NP-complete problem) unless the polynomial hierarchy collapses.
(3) On the other hand, if you're willing to talk about nonuniform algorithms (i.e., algorithms that can take "advice" depending on the input length n), then here's another "duh" observation. Suppose you have a fixed graph G on n vertices, together with a 3-coloring of G. Then you can 3-color any graph G' that happens to be isomorphic to G, provided you can compute an isomorphism between G and G'. Or if you prefer decision problems: given as advice a graph G that's 3-colorable and another graph H that isn't, and also given a decision oracle for GI, you can decide 3-colorability for those graphs that happen to be isomorphic to either G or H.
Sorry the above wasn't more helpful... :-)