Résumé : Dans cet exposé, on parlera de la notion de hom-idempotence dans l'ensemble de graphes : un graphe $G$ est dit hom-idempotent s'il existe un homomorphisme entre le graphe produit cartésien $G*G$ et $G$ lui-même. Cette notion est fortement liée à une classe particulière de graphes de Cayley qu'on appelle les graphes de Cayley normaux. On montrera que les graphes de Kneser $K(n,k)$ ne sont pas hom-idempotents. On montrera aussi que les graphes s-stables de Kneser $K(n,k)_s$ ne sont pas hom-idempotents si $s=2$ mais, pour $n=sk+1$, $K(n,k)_s$ est hom-idempotent. Finalement, on appliquera la notion de hom-idempotence à la $k$-tuple coloration de graphes : une $k$-tuple coloration de graphes consiste en affecter à chaque sommet un $k$-ensemble de couleurs de sorte que sommets adjacents reçoivent $k$-ensembles disjoints. On montrera que la différence entre le nombre chromatique du graphe produit cartésien de graphes de Kneser $K(n,k)*K(n,k)$ et le nombre chromatique d'une 2-tuple coloration du même graphe $K(n,k)*K(n,k)$ n'est pas bornée.

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr