This question already has an answer here:
For the graph colourability problem, we are given a graph and our goal is to find a colouring of the graph with the fewest possible number of colours so that no two adjacent vertices have the same colour. This problem is known to be NP complete.
Suppose that we have an algorithm $A$ that runs in polynomial time and tells us whether our graph can be coloured by using $\leq k$ colours. We can query this algorithm as many times as we want.
Would this imply that the graph colourability problem also be in $P$?
My approach would be to begin querying for $k=1$, and then keep incrementing $k$ until we get a positive response from $A$, which is going to be the answer to our problem.
However, if we know how many colours we can use to colour our graph, how do we then actually colour each node? Is there a known algorithm for this?