Things quieted down a bit and Dave said “Finding a hamiltonian cycle can't be all that hard, if someone guarantees that there is one. This extra information must be of value in the search.” Xing added “Maybe so. It seems natural that it should be easier to find something if you know it's there.” Alice asked “Does the same thing hold for chromatic number?” Bob didn't understand her question “Huh?” Alice continued, this time being careful not to even look Bob's way “I mean if someone tells you that a graph is $3$-colorable, does that help you to find a coloring using only three colors?” Dave said “Seems reasonable to me.”