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 $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 : jeudi 10 mai 2018 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr