On direct product cancellation of graphs

The direct 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. This note investigates 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 completely characterizes the situations in which cancellation holds or fails.