
BENOIT LAROSE, Champlain Regional College, Quebec, Canada 
Projective graphs and Hedetnyemi's conjecture 
Let be a finite simple graph, which for our purposes we define as a pair where is a symmetric and areflexive binary relation on the finite set G. We say that is nprojective if the only nary idempotent operations in the clone are the projections, and is nquasiprojective if all the nary idempotent operations in the clone preserve every subset of G. We prove that for all , nprojectivity, nquasiprojectivity and 2quasiprojectivity are equivalent. (the result also holds for infinite graphs). This can be used to show that complete graphs, odd cycles and Kneser graphs are nprojective for every .
These results are related to Hedetnyemi's conjecture, which states that the chromatic number of the product of two graphs is the minimum of the chromatic numbers of the factors; indeed, this conjecture can be reformulated as follows: every complete graph K_{n} is multiplicative, i.e. if K_{n} is a retract of a product then it is a retract of G or H. We show that under certain conditions, a projective graph is weakly multiplicative, i.e. that if is a retract of a product of connected graphs then it is a retract of one of the factors. In particular, complete graphs and Kneser graphs are shown to be weakly multiplicative. (Note that there exist Kneser graphs which are not multiplicative (Tardif, Zhou)).
This is joint work with C. Tardif.