MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEMinimum Chromaticity of Circulant Graphs
par Joseph Peters, Simon Fraser University, Canada
| Date : | 31/05/11 | | Time : | 15:00 | | Location : | Lagrange Gris |
Â' The circulant graph G=G^c(n;S) of order n 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_k ) mod n,Â' s_k in {s_1, s_2, ..., s_k.
In this talk, I will present families of circulant graphs for which each
graph G=G^c(n;S) has chromatic number at most 3.
First, I will present an infinite family of circulant graphs with k
chord lengths for which the chromatic number is at most 3. Then I will present an infinite family of circulant graphs with 2 chord lengths for which are 3-colourable. 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.
Page des séminaires
| 
