# 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}$ [1]. 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$)

• you can pad a hard instance with isolated vertices – Sasho Nikolov Mar 10 '13 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. – David Eppstein Mar 10 '13 at 6:05
• @Sasho How can isolated vertices help when they increase neither the chromatic number nor the maximum degree? – afshi7n Mar 10 '13 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}$ – Sasho Nikolov Mar 10 '13 at 16:35

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? – afshi7n Mar 12 '13 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$. – sangxia Mar 12 '13 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. – afshi7n Mar 12 '13 at 20:48

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.

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.. – afshi7n Mar 10 '13 at 23:05
• Why not ask Khot? – Chandra Chekuri Mar 10 '13 at 23:06
• @chandra Just sent an email and asked him, thanks for the suggestion! I will update here if I heard back. – afshi7n Mar 10 '13 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) – Michael Lampis Mar 11 '13 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? – David Eppstein Mar 11 '13 at 19:07

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$)