  In this paper we enumerate the necessary and sufficient conditions for the
weak modular product of two simple graphs to be perfect. The weak modular
product differs from the direct product by also encoding non-adjacencies of the
factor graphs in its edges. This work is motivated by the following: a 1978
theorem of Kozen states that two graphs on $n$ vertices are isomorphic if and
only if there is a clique of size $n$ in the weak modular product between the
two graphs. Furthermore, a straightforward corollary of Kozen's theorem and
Lov\'{a}sz's sandwich theorem is if the weak modular product between two graphs
is perfect, then checking if the graphs are isomorphic is polynomial in $n$.
Interesting cases include complete multipartite graphs and disjoint unions of
cliques. All perfect weak modular products have factors that fall into classes
of graphs for which testing isomorphism is already known to be polynomial in
the number of vertices.
