<p>As David pointed out, Khot's paper, "Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring", Theorem 1.6, says it is NP-hard to color $K$-colorable graph with $2^{\Omega((\log K)^2)}$ colors for graphs with degree at most $2^{2^{(\log K)^2}}$, for sufficiently large constant $K$. In other words, for graphs of degree $d$, it is hard to color $2^{\sqrt{\log\log d}}$-colorable graph with $\log d$ colors. </p>

<p>To get better degree bound, you can probably use ideas from Trevisan's paper "Non-approximability results for optimization problems on bounded degree instances". The key observation is that the graph produced by the FGLSS reduction is a union of complete bipartite subgraphs, and one can replace each of them with a bipartite disperser which is much sparser. Similar idea used in many result such as Chan <a href="http://eccc.hpi-web.de/report/2012/110/">http://eccc.hpi-web.de/report/2012/110/</a>, Theorem 1.4 / Appendix D.</p>

<p>I think this should give you something like for $2^{\sqrt{c\log d}}$-colorable graphs of degree bounded by $d$, it is NP-hard to color it with $d^{c}$ colors for some constant $0&lt;c&lt;1$.</p>

<p>The degree bound in the paper Michael mentioned is similar to Khot's, namely exponential of the soundness case. Of course the above sparsification approach also improves this, but probably won't give better constant for your purpose.</p>

CC BY-SA 3.0
2013-03-12T01:07:02.277Z
Thanks for your helpful reply, Sangxia. So, from Khot's paper, we could imply a $2^{\Omega(\log \log d)}$ hardness ratio. I think using the improvement in your paper, we can improve that hardness ratio to $2^{2^{\Omega(\sqrt{\log \log d})}}$. Is that correct?
afshi7n
CC BY-SA 3.0
2013-03-12T08:25:52.283Z
@afshi7n The parameters are a bit tricky here. Stated in terms of degree, Khot's paper gives $\log d / 2^{\sqrt{\log \log d}}$. My paper gives roughly $\log d / (\log\log d)^3$. We can improve the degree of the graph in the reduction with Trevisan's approach. I believe that gives you $d^c$. BTW all these require a sufficiently large constant $d$.
sangxia
CC BY-SA 3.0
2013-03-12T20:48:44.687Z
I see, thanks! I also asked Khot via email, he referred me to this paper http://www.siam.org/proceedings/soda/2011/SODA11_124_guruswamiv.pdf which I believe gives the $d^c$ assuming Khot's 2-1 conjecture.
afshi7n
CC BY-SA 3.0
2013-03-11T22:20:06.597Z
2013-03-11T22:20:06.597Z
sangxia
<p>There is an inapproximability result for coloring bounded degree graphs in Khot's FOCS'01 paper, "Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring" — it's probably weaker than you want, but at least it's in the right direction.</p>

<p>He proves that, for a parameter $k$ (assumed to be constant), and for $k$-chromatic graphs with degree $2^{k^{O(\log k)}}$, it is NP-hard to find colorings that use $\exp((\log k)^2/25)$ colors. So in terms of the degree $d$, it is hard to color within an $O(\log d)$ factor, but the same inapproximability ratio is also a superpolynomial function of the chromatic number.</p>

CC BY-SA 3.0
2013-03-10T23:05:54.910Z
David, thanks for your reply. Yes I had seen their result, but I'm hoping to get a hardness ratio better than $\log d$. I think this might be easier to achieve in the second problem, i.e. approximating the edge chromatic number of hypergraphs..
afshi7n
CC BY-SA 3.0
2013-03-10T23:06:39.163Z
Why not ask Khot?
Chandra Chekuri
CC BY-SA 3.0
2013-03-10T23:32:36.880Z
@chandra Just sent an email and asked him, thanks for the suggestion! I will update here if I heard back.
afshi7n
CC BY-SA 3.0
2013-03-11T19:00:43.693Z
Actually, the cited paper by Khot proves a gap between k-colorable and $k^{\log k/25}$-colorable graph (not $\exp((k\log k)/25)$. This has recently been improved by Huang to $2^{k^{1/3}}$ in a paper that will appear in the next STOC. (http://arxiv.org/abs/1301.5216)
Michael Lampis
CC BY-SA 3.0
2013-03-11T19:07:20.793Z
Why do you think that $k^{(\log k)/25}$ and $\exp((k\log k)/25)$ represent different quantities? Or am I misinterpreting the ambiguous operator precedence of Khot's formula?
David Eppstein
CC BY-SA 3.0
2013-03-11T22:04:47.053Z
@michael but unlike Khot's paper, the new paper does not provide any bounds on the degree.
afshi7n
CC BY-SA 3.0
2013-03-11T22:12:19.523Z
@DavidEppstein Maybe I am misinterpreting something, but I would think that $\exp(k\log k)=k^k$, which is much more than $k^{\log k}$. Probably I'm misreading your notation... Sorry about that.
Michael Lampis
CC BY-SA 3.0
2013-03-12T01:11:19.043Z
Oops, you're right, I'll correct it. The only reason I rewrote it was to make it more readable without the doubled superscripts.
David Eppstein
CC BY-SA 3.0
2013-03-10T21:12:25.703Z
2013-03-12T01:11:43.753Z
2013-03-12T01:11:43.753Z
David Eppstein
<p>The best known hardness of approximating the chromatic number of $3$-colorable graphs with bounded maximum degree is due to Venkatesan Guruswami and Sanjeev Khanna, <a href="http://epubs.siam.org/doi/abs/10.1137/S0895480100376794">On the Hardness of 4-Coloring a 3-Colorable Graph</a>:</p>

<blockquote>
  <p>There is a constant $\Delta$ such that given a $3$-colorable graph with
  maximum degree at most $\Delta$, it is NP-hard to color it using just $4$ colors.</p>
</blockquote>

CC BY-SA 3.0
2013-03-11T12:06:24.487Z
2013-03-11T12:06:24.487Z
vb le
<p>This result might be helpful:</p>

<p>Emden-Weinert, Hougardy, and Kreuter proved that determining whether a graph with maximum degree $\Delta$ has a coloring using $ k=$$\Delta - \sqrt\Delta +1 $   colors is NP-complete ($k\ge 3$)</p>

<p>T. Emden-Weinert, S. Hougardy, B. Kreuter, Uniquely colourable graphs and the hardness of colouring graphs of large girth, Combin. Probab. Comput. 7 (4) (1998) 375–386</p>

CC BY-SA 3.0
2013-03-11T00:10:12.023Z
2013-03-11T00:15:23.577Z
2013-03-11T00:15:23.577Z
Mohammad Al-Turkistany
<p>I am looking for hardness results on vertex coloring of graphs with bounded degree. </p>

<p>Given a graph $G(V,E)$, we know that for any $\epsilon&gt;0$, it's hard to approximate $\chi(G)$ within a factor of $|V|^{1-\epsilon}$ unless $\textit{NP}=\textit{ZPP}$ [<a href="http://www.sciencedirect.com/science/article/pii/S0022000098915872">1</a>]. But what if the maximum degree of $G$ is bounded by $d$? Are there any hardness ratios of the form $d^{1-\epsilon}$ (for some $\epsilon$) in this case?</p>

<p>An easier question is: Hardness of approximating the edge-chromatic-number of hypergraphs when their edge size is bounded by $d$. Can we hope for a $d^{1-\epsilon}$ hardness ratio in this case? (say, for any $\epsilon &gt;0$)</p>

<p>Thanks for your attention!</p>

CC BY-SA 3.0
2013-03-10T05:02:40.647Z
you can pad a hard instance with isolated vertices
Sasho Nikolov
CC BY-SA 3.0
2013-03-10T06:05:35.130Z
Yes, but if you put a finite bound on the size of the hard instance  that you start from, it stops being hard.
David Eppstein
CC BY-SA 3.0
2013-03-10T06:49:42.460Z
@Sasho How can isolated vertices help when they increase neither the chromatic number nor the maximum degree?
afshi7n
CC BY-SA 3.0
2013-03-10T16:35:26.627Z
@DavidEppstein sure, this padding only proves something if $n$ and $d$ are still polynomially related. OP, that is actually precisely the point. you start with an instance with $d$ vertices (so max degree at most $d$) for which it is hard to approximate $\chi$ to within $d^{1-\epsilon}$. add $n - d$ isolated vertices. $\chi$ stays the same and max degree stays $d$. this is polytime if $N = d^{O(1)}$. so for any integer $k$, there exist instances with max degree $d = n^{1/k}$ for which it is hard to approximate $\chi$ to within $d^{1-\epsilon}$
Sasho Nikolov
CC BY-SA 4.0
2020-02-25T10:29:24.110Z
Update: It is NP-hard to approximate $\chi(G)$ within a factor of $|V|^{1-\epsilon}$ without any extra assumptions.
Cyriac Antony
<cc.complexity-theory><approximation-hardness><graph-colouring><hypergraphs><bounded-degree>
hardness of approximating the chromatic number in graphs with bounded degree
afshi7n
# hardness of approximating the chromatic number in graphs with bounded degree

(Asked by: username_0 on 2013-03-10)

I am looking for hardness results on vertex coloring of graphs with bounded degree.

Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor of $|V|^{1-\epsilon}$ unless $\textit{NP}=\textit{ZPP}$ [[1](http://www.sciencedirect.com/science/article/pii/S0022000098915872)]. But what if the maximum degree of $G$ is bounded by $d$? Are there any hardness ratios of the form $d^{1-\epsilon}$ (for some $\epsilon$) in this case?

An easier question is: Hardness of approximating the edge-chromatic-number of hypergraphs when their edge size is bounded by $d$. Can we hope for a $d^{1-\epsilon}$ hardness ratio in this case? (say, for any $\epsilon >0$)

Thanks for your attention!

**Tags:** cc.complexity-theory, approximation-hardness, graph-colouring, hypergraphs, bounded-degree
> **Comments:**
> **username_1**: you can pad a hard instance with isolated vertices  
> **username_2**: Yes, but if you put a finite bound on the size of the hard instance  that you start from, it stops being hard.  
> **username_0**: @Sasho How can isolated vertices help when they increase neither the chromatic number nor the maximum degree?  
> **username_1**: @DavidEppstein sure, this padding only proves something if $n$ and $d$ are still polynomially related. OP, that is actually precisely the point. you start with an instance with $d$ vertices (so max degree at most $d$) for which it is hard to approximate $\chi$ to within $d^{1-\epsilon}$. add $n - d$ isolated vertices. $\chi$ stays the same and max degree stays $d$. this is polytime if $N = d^{O(1)}$. so for any integer $k$, there exist instances with max degree $d = n^{1/k}$ for which it is hard to approximate $\chi$ to within $d^{1-\epsilon}$  
> **username_3**: Update: It is NP-hard to approximate $\chi(G)$ within a factor of $|V|^{1-\epsilon}$ without any extra assumptions.  

---

## 4 answers

### Answer by username_4 on 2013-03-11. Score: 10

As David pointed out, Khot's paper, "Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring", Theorem 1.6, says it is NP-hard to color $K$-colorable graph with $2^{\Omega((\log K)^2)}$ colors for graphs with degree at most $2^{2^{(\log K)^2}}$, for sufficiently large constant $K$. In other words, for graphs of degree $d$, it is hard to color $2^{\sqrt{\log\log d}}$-colorable graph with $\log d$ colors.

To get better degree bound, you can probably use ideas from Trevisan's paper "Non-approximability results for optimization problems on bounded degree instances". The key observation is that the graph produced by the FGLSS reduction is a union of complete bipartite subgraphs, and one can replace each of them with a bipartite disperser which is much sparser. Similar idea used in many result such as Chan <http://eccc.hpi-web.de/report/2012/110/>, Theorem 1.4 / Appendix D.

I think this should give you something like for $2^{\sqrt{c\log d}}$-colorable graphs of degree bounded by $d$, it is NP-hard to color it with $d^{c}$ colors for some constant $0

The degree bound in the paper Michael mentioned is similar to Khot's, namely exponential of the soundness case. Of course the above sparsification approach also improves this, but probably won't give better constant for your purpose.

> **Comments:**
> **username_0**: Thanks for your helpful reply, Sangxia. So, from Khot's paper, we could imply a $2^{\Omega(\log \log d)}$ hardness ratio. I think using the improvement in your paper, we can improve that hardness ratio to $2^{2^{\Omega(\sqrt{\log \log d})}}$. Is that correct?  
> **username_4**: @afshi7n The parameters are a bit tricky here. Stated in terms of degree, Khot's paper gives $\log d / 2^{\sqrt{\log \log d}}$. My paper gives roughly $\log d / (\log\log d)^3$. We can improve the degree of the graph in the reduction with Trevisan's approach. I believe that gives you $d^c$. BTW all these require a sufficiently large constant $d$.  
> **username_0**: I see, thanks! I also asked Khot via email, he referred me to this paper http://www.siam.org/proceedings/soda/2011/SODA11_124_guruswamiv.pdf which I believe gives the $d^c$ assuming Khot's 2-1 conjecture.  

---

### Answer by username_2 on 2013-03-10. Score: 9

There is an inapproximability result for coloring bounded degree graphs in Khot's FOCS'01 paper, "Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring" — it's probably weaker than you want, but at least it's in the right direction.

He proves that, for a parameter $k$ (assumed to be constant), and for $k$-chromatic graphs with degree $2^{k^{O(\log k)}}$, it is NP-hard to find colorings that use $\exp((\log k)^2/25)$ colors. So in terms of the degree $d$, it is hard to color within an $O(\log d)$ factor, but the same inapproximability ratio is also a superpolynomial function of the chromatic number.

> **Comments:**
> **username_0**: David, thanks for your reply. Yes I had seen their result, but I'm hoping to get a hardness ratio better than $\log d$. I think this might be easier to achieve in the second problem, i.e. approximating the edge chromatic number of hypergraphs..  
> **username_5**: Why not ask Khot?  
> **username_0**: @chandra Just sent an email and asked him, thanks for the suggestion! I will update here if I heard back.  
> **username_6**: Actually, the cited paper by Khot proves a gap between k-colorable and $k^{\log k/25}$-colorable graph (not $\exp((k\log k)/25)$. This has recently been improved by Huang to $2^{k^{1/3}}$ in a paper that will appear in the next STOC. (http://arxiv.org/abs/1301.5216)  
> **username_2**: Why do you think that $k^{(\log k)/25}$ and $\exp((k\log k)/25)$ represent different quantities? Or am I misinterpreting the ambiguous operator precedence of Khot's formula?  
> **username_0**: @michael but unlike Khot's paper, the new paper does not provide any bounds on the degree.  
> **username_6**: @DavidEppstein Maybe I am misinterpreting something, but I would think that $\exp(k\log k)=k^k$, which is much more than $k^{\log k}$. Probably I'm misreading your notation... Sorry about that.  
> **username_2**: Oops, you're right, I'll correct it. The only reason I rewrote it was to make it more readable without the doubled superscripts.  

---

### Answer by username_7 on 2013-03-11. Score: 8

The best known hardness of approximating the chromatic number of $3$-colorable graphs with bounded maximum degree is due to Venkatesan Guruswami and Sanjeev Khanna, [On the Hardness of 4-Coloring a 3-Colorable Graph](http://epubs.siam.org/doi/abs/10.1137/S0895480100376794):

> There is a constant $\Delta$ such that given a $3$-colorable graph with
> maximum degree at most $\Delta$, it is NP-hard to color it using just $4$ colors.


---

### Answer by username_8 on 2013-03-11. Score: 5

This result might be helpful:

Emden-Weinert, Hougardy, and Kreuter proved that determining whether a graph with maximum degree $\Delta$ has a coloring using $ k=$$\Delta - \sqrt\Delta +1 $ colors is NP-complete ($k\ge 3$)

T. Emden-Weinert, S. Hougardy, B. Kreuter, Uniquely colourable graphs and the hardness of colouring graphs of large girth, Combin. Probab. Comput. 7 (4) (1998) 375–386


---

