On multiplicative graphs and the product conjecture (Q1110530)

A graph is called multiplicative if the class of all graphs not admitting a homomorphism into G is closed under taking the product of graphs. The authors study the multiplicativity of some families of graphs and their investigation is motivated by the product conjecture of Hedetniemi which asserts that all complete undirected graphs are multiplicative. One of the results of this paper provides the first non-trivial infinite family of multiplicative undirected graphs, namely the odd cycles. Another result, conjectured by Nešetřil and Pultr and proved by the authors is that the directed cycles of prime power length are also multiplicative. These two results, together with some simple remarks, give a complete characterization of all directed and undirected cycles which are multiplicative.