Polynomial vertex coloring algorithm

Question

Assume that we have an polynomial algorithm $C(G, k)$ such that it defines if it is possible or not to make vertex coloring of graph $G$ in $k$ colors. Prove that there is an polynomial algorithm $D(G, k)$ such that it returns a vertex coloring of graph $G$ in $k$ colors. In the case it's not possible the algorithm returns that 'it is not possible'.

Answer 1

Let $G,k$ be the input of $D$. Let $\star_1,\dots,\star_k$ be new vertices, and let $V'$ be the set $V(G) \cup \{\star_1,\dots,\star_k\}$. For a graph $H$ on $V'$, a vertex $v\in V(G)$ and $k'\in\{1,\dots,k\}$, define $H_{+(v,k')}$ to be the graph whose vertices are $V'$, that contains all the edges of $H$ and edges $\{v,\star_i\}$ for every $i\neq k'$.

The algorithm works as follows: at any step, we keep a graph H on $V'$ such that for every $v\in V$, either $v$ is not connected to any $\star_i$ or $v$ is connected to all $\star_i$'s except one. Initially, the graph is $G$ to which we add $\{\star_1,\dots,\star_k\}$ as an isolated clique. Then we do the following:

• pick a vertex $v$ of $H$ that is not connected to any $\star_i$. If no such vertex exists, for each vertex of $V$ there is a unique $i$ such that $\{v,\star_i\}$ is not an edge of $H$. This $i$ gives you a colour for each vertex, which is a colouring of the graph.
• for every $k'\in\{1,\dots,k\}$, build the graph $H_{+(v,k')}$. Use $C$ to test if $H_{+(v,k')}$ is colourable. If it is, replace $H$ by $H_{+(v,k')}$. Otherwise try another $k'$. If for every $k'\in\{1,\dots,k\}$, the algorithm $C$ returns that $H_{+(v,k')}$ is not colourable, then return "not possible".

It is clear that the running time is polynomial, if $C$ runs in polynomial time.

The idea of the algorithm is that you check for an arbitrary vertex $v$ and an integer $k'$ whether there exists a colouring of $G$ that assigns the colour $k'$ to $v$. Of course, $G$ is $k$-colourable iff for at least one $k'$ this is the case and the resulting partially coloured graph is colourable. So you just continue imposing more and more constraints until you found a proper colouring of $G$. The new vertices $\star_1,\dots,\star_k$ form a gadget that allows to force $C$ to only consider colouring with some colours imposed.