Using the chromatic number to compute an optimal coloring

Suppose we are given a graph $G$ of order $n$ and a black box that can efficiently (polynomial time) compute the chromatic number $\chi(G)$. I am curious to hear how would one go about in order to construct a proper coloring of $G$, more precisely

Find an efficient algorithm (polynomial time) to construct a proper coloring of $G$ provided that you can efficiently compute the chromatic number.

Does anybody see a simple algorithm for this purpose?

As long as possible, add edges to $G$ which do not increase the chromatic number. You should get a complete multipartite graph which corresponds to an optimal coloring.

StackExchange Computer Science Q#144470, answer score: 3