Loading [MathJax]/jax/output/HTML-CSS/jax.js

Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 15 mai 2018 à 14h00 en B107, Mario Valencia-Pabon nous parlera de : Hom-idempotent graphs, normal Cayley graphs and stable Kneser graphs

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 GG 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 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr