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.