  Since the seminal result of Karger, Motwani, and Sudan, algorithms for
approximate 3-coloring have primarily centered around SDP-based rounding.
However, it is likely that important combinatorial or algebraic insights are
needed in order to break the $n^{o(1)}$ threshold. One way to develop new
understanding in graph coloring is to study special subclasses of graphs. For
instance, Blum studied the 3-coloring of random graphs, and Arora and Ge
studied the 3-coloring of graphs with low threshold-rank.
  In this work, we study graphs which arise from a tensor product, which appear
to be novel instances of the 3-coloring problem. We consider graphs of the form
$H = (V,E)$ with $V =V( K_3 \times G)$ and $E = E(K_3 \times G) \setminus E'$,
where $E' \subseteq E(K_3 \times G)$ is any edge set such that no vertex has
more than an $\epsilon$ fraction of its edges in $E'$. We show that one can
construct $\widetilde{H} = K_3 \times \widetilde{G}$ with $V(\widetilde{H}) =
V(H)$ that is close to $H$. For arbitrary $G$, $\widetilde{H}$ satisfies $|E(H)
\Delta E(\widetilde{H})| \leq O(\epsilon|E(H)|)$. Additionally when $G$ is a
mild expander, we provide a 3-coloring for $H$ in polynomial time. These
results partially generalize an exact tensor factorization algorithm of Imrich.
On the other hand, without any assumptions on $G$, we show that it is NP-hard
to 3-color $H$.
