  Computing the clique number and chromatic number of a general graph are
well-known NP-Hard problems. Codenotti et al. (Bruno Codenotti, Ivan Gerace,
and Sebastiano Vigna. Hardness results and spectral techniques for
combinatorial problems on circulant graphs. \emph{Linear Algebra Appl.},
285(1-3): 123--142, 1998) showed that computing clique number and chromatic
number are still NP-Hard problems for the class of circulant graphs. We show
that computing clique number is NP-Hard for the class of Cayley graphs for the
groups $G^n$, where $G$ is any fixed finite group (e.g., cubelike graphs). We
also show that computing chromatic number cannot be done in polynomial time
(under the assumption $\text{P}\neq \text{NP}$) for the same class of graphs.
Our presentation uses free Cayley graphs. The proof combines free Cayley graphs
with quotient graphs and Goppa codes.
