I have some doubts on the inapproximability result for acyclic coloring presented in the paper New acyclic and star coloring algorithms with application to computing Hessians. They claim that there exist an $\epsilon>0$ such that acyclic coloring cannot be approximated within $O(n^\epsilon)$ unless $\textsf{P=NP}$. It is proved by means of a reduction from Coloring.
Given an instance $G$ of Coloring, an graph $H$ is constructed by replacing each edge $e=uv$ of $G$ by $\Delta=\Delta(G)$ parallel edges and subdividing them exactly once. The construction has the following properties. They prove that for all $p$ in $3\leq p\leq \Delta$, $\chi(G)\leq p \iff \chi_s(H)\leq p$. From this, and the result Chromatic number is NP-hard to approximate within $O(n^\epsilon)$ for some $\epsilon>0$, they conclude that Acyclic chromatic number is NP-hard to approximate within $O(n^\epsilon)$ for some $\epsilon>0$.
(In the above paragraph, $\Delta(G)$ denotes the maximum degree of $G$ ).
What type of reduction is this? I am assuming it is the basic type gap-preserving reduction presented in Vazirani's book (see quote below).
The details of the gap-preserving reduction are not clear to me. I think it is proved using a gap-preserving reduction.(Disclaimer: I don't know whether they are using some specific type of approximation preserving reduction such as L-reduction).
This is my best guess on the reduction. Clearly,
$\chi(G)\leq 3 \implies \chi_s(H)\leq 3$,
$\chi(G)>\Delta \implies \chi_s(H)>\Delta$
Let me recall definition for gap-preserving reduction from Vazirani's book here (slightly modified to fit this context).
A gap-preserving reduction from minimization problem A to minimization problem B with parameters $f,\alpha,g,\beta$ maps an instance $x$ of A to an instance $y$ of B such that
$\bullet\ $ the mapping is poly. time computable,
$\bullet\ $ $OPT\leq f(x) \implies OPT\leq g(y)$, and
$\bullet\ $ $OPT>\alpha(|x|)\ f(x) \implies OPT>\beta(|y|)\ g(y)$.
(Also for all $x$ and $y$, $\alpha(|x|)>1$ and $\beta(|y|)>1$. OPT refers to optimal value for problem A when used on left side, and problem B when used on right side.)
Here, it seems $f_A=f_B=3$ and $\alpha(|x|)=\beta(|y|)=\Delta/3$. But, here $|x|=n+m$ and $|y|=(n+\Delta m)+2\Delta m$ (where $n=$ #vertices in $G$, and $m=$ #edges in $G$). But then, functions $\alpha$ and $\beta$ cannot be defined like this!
What are the correct functions $f,g,\alpha,\beta$ implicit in the inpproximability proof of the paper?