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

<p>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.</p>

CC BY-SA 3.0
2011-04-25T22:35:10.520Z
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.
Andrew D. King
CC BY-SA 3.0
2011-04-25T20:34:45.087Z
2011-04-25T20:34:45.087Z
David Eppstein
<p>Let $G$, with $\chi(G) \geq 3$ (otherwise you have an exact algorithm).</p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2011-04-25T20:41:18.577Z
2011-04-25T20:41:18.577Z
Vinicius dos Santos
<p>In paper <em>Approximation Algorithms for the Chromatic Sum</em>, 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$.</p>

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

<p>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.</p>

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

CC BY-SA 3.0
2011-04-26T01:26:50.090Z
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$.
Jeffε
<approximation-algorithms><approximation-hardness><graph-colouring>
Hardness of additive approximation to Graph Coloring problem.
Buss
# Hardness of additive approximation to Graph Coloring problem.

(Asked by: username_0 on 2011-04-25)

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.

**Tags:** approximation-algorithms, approximation-hardness, graph-colouring
> **Comments:**
> **username_1**: 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$.  

---

## 2 answers

### Answer by username_4 on 2011-04-25. Score: 11 | Accepted answer

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 by username_2 on 2011-04-25. Score: 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.

> **Comments:**
> **username_3**: 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.  

---

