  For a graph $H$ and integer $k \geq 1$, two functions $f, g$ from $V(H)$ into
$\{1, \dots, k\}$ are adjacent if for all edges $uv$ of $H$, $f(u) \neq g(v)$.
The graph of all such functions is the exponential graph $K_k^H$. El-Zahar and
Sauer proved that if $\chi(H) \geq 4$, then $K_3^H$ is 3-chromatic. Tardif
showed that, implicit in their proof, is an algorithm for 3-coloring $K_3^H$
whose time complexity is polynomial in the size of $K_3^H$. Tardif then asked
if there is an "explicit" algorithm for finding such a coloring: Essentially,
given a function $f$ belonging to a 3-chromatic component of $K_3^H$, can we
assign a color to this vertex in time polynomial in the size of $H$? The main
result of this paper is to present such an algorithm, answering Tardif's
question affirmatively. Our algorithm yields an alternative proof of the
theorem of El-Zahar and Sauer that the categorical product of two 4-chromatic
graphs is 4-chromatic.
