# hardness of approximating the chromatic number in graphs with bounded degree

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}$ . 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!

• you can pad a hard instance with isolated vertices Mar 10, 2013 at 5:02
• Yes, but if you put a finite bound on the size of the hard instance that you start from, it stops being hard. Mar 10, 2013 at 6:05
• @Sasho How can isolated vertices help when they increase neither the chromatic number nor the maximum degree? Mar 10, 2013 at 6:49
• @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}$ Mar 10, 2013 at 16:35
• Update: It is NP-hard to approximate $\chi(G)$ within a factor of $|V|^{1-\epsilon}$ without any extra assumptions. Feb 25, 2020 at 10:29

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<c<1$.

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.

• 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? Mar 12, 2013 at 1:07
• @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$. Mar 12, 2013 at 8:25
• I see, thanks! I also asked Khot via email, he referred me to this paper siam.org/proceedings/soda/2011/SODA11_124_guruswamiv.pdf which I believe gives the $d^c$ assuming Khot's 2-1 conjecture. Mar 12, 2013 at 20:48

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.

• 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.. Mar 10, 2013 at 23:05
• Why not ask Khot? Mar 10, 2013 at 23:06
• @chandra Just sent an email and asked him, thanks for the suggestion! I will update here if I heard back. Mar 10, 2013 at 23:32
• 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. (arxiv.org/abs/1301.5216) Mar 11, 2013 at 19:00
• 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? Mar 11, 2013 at 19:07

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:

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.

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