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 : Friday 10 January 2025 | Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |