[tromp]

> it has no good decision problem associated with it.

I disagree. You can efficiently find a k-coloring of any k-colorable graph if you can efficiently decide what graphs are k-colorable.