Abstract. The direct (or tensor) product of graphs obeys a limited cancellation property. Lovász proved that if C
has an odd cycle then A × C = B × C if and only if A = B, but
cancellation can fail if C is bipartite. We investigate the ways
cancellation can fail. Given a graph A and a bipartite graph C,
we classify the graphs B for which A × C = B × C.
Further, we give exact conditions on A that guarantee A × C = B × C implies A = B.
Combined with Lovász’s result, this characterizes the situations in which cancellation holds or fails.
More on direct product cancellation of graphs