Evènement pour le groupe GT Graphes et Applications


Date 2013-02-15  14:00-15:00
Titre3-Colourable Circulant Graphs  
Résumé The circulant graph G(n;S) is a graph on vertex set V={v_0,v_1, ...,v_(n-1)} with an edge joining v_i and v_j whenever i =(j + s) mod n for s in {s_1, s_2, ..., s_k}. In this talk, I will present infinite families of circulant graphs for which each graph G(n;S) has chromatic number 3. First, I will present a family of 3-colourable circulant graphs with k chord lengths. Then I will present a family of 3-colourable circulant graphs with 2 chord lengths. I will also show that recursive circulant graphs and a class of optimal double loop graphs are 3-colourable. This is joint work with Nenad Obradovic and Goran Ruzic.  
LieuSalle 178 
OrateurJoseph Peters 
UrlSimon Fraser University, Canada 



Aucun document lié à cet événement.

Retour
Retour à l'index