Evènement pour le groupe GT Graphes et Applications

Date 2011-11-04  14:00-15:00
TitreRainbow numbers and rainbow connection  
RésuméIn this talk we consider edge colourings of graphs. A subgraph H of a graph G is called rainbow subgraph, if all its edges are coloured distinct. In the first part we will survey the computation of rainbow numbers. For given graphs G,H the rainbow number rb(G,H) is the smallest number m of colours such that if we colour the edges of G with at least m different colours, then there is always a totally multicoloured or rainbow copy of H. For various graph classes of H we will list the known rainbow numbers if G is the complete graph and report about recent progress on the computation of rainbow numbers. Finally, new results on the rainbow numbers rb(Qn,Qk) for the hypercube Qn will be presented. An edge-coloured graph G is called rainbow connected if any two vertices are connected by a path whose edges have distinct colours. This concept of rainbow connection in graphs was introduced by Chartrand et al.. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow connected. In the second part we will show several complexity results and present lower and upper bounds for rc(G). We will discuss rc(G) for graphs with given minimum degree. Finally, we will present some recent Erdös-Gallai type results for rc(G). 
LieuSalle 178 
OrateurIngo Schiermeyer  

Aucun document lié à cet événement.

Retour à l'index