Solving the graph colourability problem in polynomial time if the equivallent decision problem is in $P$
Hint: If there is a valid coloring in which vertices $x,y$ get the same color then the graph resulting from merging $x,y$ into a single vertex has the same chromatic number. Otherwise, you can add an edge between them (if it doesn't already exist). Either way, the graph "simplifies" (either the number of vertices decreases, or the graph gets closer to a clique).