On multiplicative graphs and the product conjecture

We study the following problem: which graphsG have the property that the class of all graphs not admitting a homomorphism intoG is closed under taking the product (conjunction)? Whether all undirected complete graphs have the property is a longstanding open problem due to S. Hedetniemi. We prove that all odd undirected cycles and all prime-power directed cycles have the property. The former result provides the first non-trivial infinite family of undirected graphs known to have the property, and the latter result verifies a conjecture of Nešetřil and Pultr These results allow us (in conjunction with earlier results of Nešetřil and Pultr [17], cf also [7]) to completely characterize all (finite and infinite, directed and undirected) paths and cycles having the property. We also derive the property for a wide class of 3-chromatic graphs studied by Gerards, [5].