Hardness of additive approximation to Graph Coloring problem.

Question

In paper Approximation Algorithms for the Chromatic Sum, page 18, authors state that based on the fact that the Graph Coloring problem is hard to approximate with a ratio less than 2 (under the assumption of $P \neq NP$), it's easy to show that for any constant $k$, there is no approximate algorithm $A$ to Graph Coloring such that $\chi(G) \leq A(G) \leq \chi(G) + k$.

But i can't see how to show/prove this.

As i see, it isn't so direct, because for any $k$, there are graphs such that $\chi(G) \leq k$, so for them $\chi(G) + k \geq 2 \cdot \chi(G)$ and it would be $(2 + \epsilon)$-approximative, for some $\epsilon \geq 0$, for these graphs.

So i'm asking for some help/advice on how to show/prove this.

Answer 1

Let $G$, with $\chi(G) \geq 3$ (otherwise you have an exact algorithm).

Now construct a graph $H$ consisting of $k$ copies $G_1,\ldots,G_k$ of $G$, with all possible edges between $u$ and $v$ for $u \in G_i$, $v \in G_j$, $i\not=j$.

Now use the additive constant algorithm for the graph $H$, which will find a coloring of, at most, $k\cdot\chi(G) + k$ colors. Since the colors in each copy of $G$ will be distinct, by the Pigeonhole principle, you have one of the copies with at most $\chi(G)+1$ distinct colors, which is better than a 2-approximation.

Answer 2

It is easy to show hardness of additive approximation based on nonconstant multiplicative inapproximability bounds, which are known.

My guess is that they were thinking of the following construction: starting from a graph G that is hard to color, replace every vertex by a k-clique. If it were true that this replacement multiplies the chromatic number by k, then it would be hard to find an additive approximation to the coloring of the larger graph. But, it's not true; e.g. C5 requires three colors but 2xC5 requires only five, not six.