Algorithm for valid 3 coloring.

Question

If we have P=NP, how can I show that a polynomial algorithm exists that given any 3 colourable graph produces a valid 3 colouring (no two adjacent vertices share the same colour)?

Answer 1

Assuming P=NP, one has a polynomial-time algorithm to decide, given a graph $G$, if $G$ is 3-colourable or not. One can assume that the algorithm is also able to detect if a graph is 3-colourable given a partial colouration of its nodes (i.e it answers the question "is there a 3-colouring that extends the colouring given as input?"), because this problem is NP-complete too. Let us call this algorithm $\mathcal A$.

Then an algorithm $\mathcal B$ to produce a valid colouring can be as follows on the input $G=(\{1,\ldots,n\}, E)$ and $\chi$ a partial function from $\{1,\ldots,n\}$ to $\{1,2,3\}$:

Pick $v$ not in the domain of $\chi$. For $j \in \{1,2,3\}$, give to $v$ the colour $j$ and ask $\mathcal A$ if $G$ is 3-colourable, partially coloured with $\chi\cup (v\mapsto j)$. If this is the case, call $\mathcal B$ with input $G$ and $\chi\cup (v\mapsto j)$. If no colour can be attributed to $v$ then reject. Otherwise when the domain of $\chi$ is $\{1,\ldots,n\}$ accept and return $\chi$.

This algorithm runs in polynomial-time assuming $\mathcal A$ does, and on the input $(G,\emptyset)$ it builds a 3-colouring of $G$ or reject if no colouring exists.