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].