A note on polynomial approximation of synchronizing optimal coloring

A strongly connected aperiodic directed graph with constant out-degree is called admissible. An automaton $A$ is a coloring of admissible graph $G$ if the underlying graph of $A$ equals $G$. A word is called synchronizing for an automaton $A$ if it takes $A$ to a one particular state no matter of the starting state. Optimal coloring of admissible graph $G$ is a synchronizing coloring with shortest reset word among all synchronizing colorings of $G$. The length of the corresponding reset word is called optimal coloring value. We prove that unless $\mathcal P=\mathcal{NP}$, no polynomial-time algorithm approximates optimal coloring or optimal coloring value within a factor less than 2 in the 3-letter alphabet case. We also extend this result to the 2-letter alphabet case.