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$)Thanks for your attention!
hardness of approximating the chromatic number in graphs with bounded degree
cc.complexity theory;approximation hardness;graph colouring;hypergraphs;bounded degree