ISSN:
1439-6912
Keywords:
05 C 15
;
05 C 20
;
05 C 38
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract 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].
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02122553
Permalink
