CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  Eventssee all events
Events        
next up previous
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 Kn is multiplicative, i.e. if Kn 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 up previous
Next: Jonathan Leech - Noncommutative Up: Universal Algebra and Multiple-Valued Previous: Jennifer Hyndman - Dualizable
 

© Canadian Mathematical Society, 2017 : https://cms.math.ca/