The following roughly sketched algorithm, assuming P=NP, finds a 3 coloring of the input graph if one exists, in polynomial time. If there's no such 3 coloring, though, it never terminates.
First, learn to enumerate all possible algorithms (Turing machines), and to simulate computation of any such Turing machine on arbitrary input.
Second, learn to enumerate all possible algorithms with an attached poly-time alarm clock. (That means that we will be enumerating a special case of Turing machines that conceptually do two things in parallel; on one set of tapes, they compute the "primary problem", and on a separate tape they just count down to zero from a fixed one of functions n, 2*n^2, 3*n^3, ..., where n is the length of the input to the primary problem, halting the computation (perhaps prematurely from the perspective of the primary problem) once this countdown on the separate tape (called alarm clock) reaches zero before the primary problem is solved. So sometimes the computation is terminated because an output has been provided for the primary problem, and sometimes the computation is terminated by the alarm clock, with the output tape containing whatever it happens to.)
The exact order in which the Turing machines with an attached polynomial alarm clock are enumerated should be exhaustive: it should be such that we'll encounter every combination of a Turing machine and of an alarm clock function among the ones suggested above sooner or later.
Now, learn to simulate all these Turing machines with an attached polynomial alarm clock in parallel, starting them well spaced in time one by one. In particular, make sure that almost one half of the total running time is devoted to the first Turing machine with an attached polynomial alarm clock in the enumeration, almost one quarter of total running time to the second machine, almost one eighth of it to the third machine and so on. (We are making sure that each Turing machine in the enumeration gets a known constant fraction range of total run time, assuming we keep running at least till its first transition.)
How can we do that? Example: Simulate one transition of the first machine. Then the same again - one more transition of the first machine. Then one transition of the second machine. Than all this again: two more transitions of the first machine and one more of the second machine. Only then do the first transition of the third machine, followed by all that again (seven more transitions in total) before ever simulating the first transition of the fourth machine.
From time to time, a machine terminates, be it due to its alarm clock or to its having solved its primary problem (which will rarely consist of a production of 3 colorings of the input graph, but who cares). If a machine terminated, we check whether it has produced a valid 3 coloring of the input graph on its output tape, and if so, we terminate the entire simulation of all the Turing machines with attached alarm clocks, returning the same 3 coloring as the output.
To be honest, I haven't closely checked that I can amortize the overhead of switching attention from a machine to a machine, the overhead of iterating across the machines (i.e., generating the initial state of a new machine in the enumeration), and the overhead of checking the terminal states (whether a terminating machine stumbled upon a valid 3 coloring or not); but I can certainly make sure to spend more time on the simulated transitions of individual Turing machines than on all these kinds of overhead, i.e. the total overhead ends up less than 100%, again a constant factor.
Now, it is well known that the function version of the 3 coloring problem is self reducible to its decision version. There's a simple polynomial time algorithm for the decision problem (by P=NP) and therefore the self-reducing algorithm which actually reliably identifies an example 3 coloring in polynomial time whenever one exists, occurs somewhere in our enumeration of all Turing machines - and it occurs somewhere even with a liberal enough polynomial time alarm clock which allows it to complete in whatever time it needs. Good news is that we gave a fixed fraction of attention (of the time resource) to this particular machine in our multitasking simulation, therefore we have slowed it down just by a (huge) constant factor - by the other simultaneously simulated machines, and by the remaining up to 100% overhead. So even this specific "universal" simulation is capable of providing examples of 3 coloring in polynomial time. Quod erat promissum.
(I'd love to say that this simulation comes close to preserving even the optimum exponent of finding the 3 coloring, but that just wouldn't be true. The biggest problem in this respect is that the "universal" simulator may have fewer tapes and fewer states than the machine being simulated, and simulating even a single transition is a costly exercise; the simulation preserves polynomial time, but not the specific exponent.)
Unfortunately, any such simulation only becomes a polynomial time algorithm for finding 3-colorings if we now equip it with its own polynomial time alarm clock (thus slowing it down twice, and also guaranteeing that it terminates on any input within the specified time limit); and this last step is con-constructive. Unlike any part of the construction until now, we don't know which polynomial among n, 2*n^2, 3*n^3, ... should be chosen for the alarm clock. We just know that a sufficiently liberal alarm clock exists, such that if we attach it to our (otherwise specific) "universal" machine, we will obtain a polynomial time algorithm doing 3 colorings wherever they exist and rejecting (only) graphs that are not 3 colorable, or inputs that do not encode graphs.
The method of universal simulation can be extended even to your graph coloring problem with the help of the additional technique described in this answer. What gets messier is that we are then no longer able to filter out "wrong answers" that easily; if a machine offers us a 5-coloring, how do we know whether a 4-coloring exists? The sufficient solution is to just wait it out, either a 4-coloring will appear in the output of a better behaved child machine or not, before the master alarm clock runs out. Again, the last step will be non-constructive: we know that with a sufficiently liberal polynomial time alarm clock we'd get a polynomial algorithm giving us optimal colorings, but it's hard to tell which specific polynomial to choose if all we know is that P=NP. If we choose a too aggressive (insufficient) polynomial time alarm clock, not only we will sometimes fail to find the optimal coloring, but we will sometimes output a suboptimal coloring which we tried to wait out, but not patiently enough.