Benoit Larose - Projective graphs and Hedetnyemi's conjecture

Next: Jonathan Leech - Noncommutative Up: Universal Algebra and Multiple-Valued Previous: Jennifer Hyndman - Dualizable

Benoit Larose - Projective graphs and Hedetnyemi's conjecture

BENOIT LAROSE, Champlain Regional College, Quebec, Canada

Projective graphs and Hedetnyemi's conjecture

Let $\bf G$ be a finite simple graph, which for our purposes we define as a pair $\bf G = \langle G,\theta \rangle$ where $\theta$ is a symmetric and areflexive binary relation on the finite set G. We say that $\bf G$ is n-projective if the only n-ary idempotent operations in the clone $\textrm{Pol}\theta$ are the projections, and $\bf G$ is n-quasiprojective if all the n-ary idempotent operations in the clone $\textrm{Pol}\theta$ preserve every subset of G. We prove that for all $n \geq 2$ , n-projectivity, n-quasiprojectivity and 2-quasiprojectivity are equivalent. (the result also holds for infinite graphs). This can be used to show that complete graphs, odd cycles and Kneser graphs are n-projective for every $n \geq 2$ .

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 $G \times H$ then it is a retract of G or H. We show that under certain conditions, a projective graph $\bf P$ is weakly multiplicative, i.e. that if $\bf P$ 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.

Next: Jonathan Leech - Noncommutative Up: Universal Algebra and Multiple-Valued Previous: Jennifer Hyndman - Dualizable