# Hardness of additive approximation to Graph Coloring problem.

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.

• I regularly ask this problem on exams. You don't even need hadness of approximation; there is a simple argument directly from the exact problem's NP-hardness. Given a graph G, consider a graph H consisting of 2k distinct copies of G, with edges between any two vertices in distinct copies. If $\chi(H)\le x \le \chi(H)+ k$, then $\chi(G) = \lfloor x/k \rfloor$. Apr 26, 2011 at 1:26

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.
• This actually approaches $k$ times the fractional chromatic number as $k$ grows. You want to join together $k$ copies of the graph, instead. The strong product of $K_2$ and $C_5$, for example, is 5, which two joined copies of $C_5$ have chromatic number 6. Apr 25, 2011 at 22:35