19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Rainbow numbers and rainbow connection

Presented by Prof. Ingo SCHIERMEYER
Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs


\begin{abstract} In this talk we consider edge colourings of graphs. A subgraph $H$ of a graph $G$ is called {\it 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(Q_n, Q_k)$ for the hypercube $Q_n$ will be presented. An edge-coloured graph $G$ is called {\it 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 {\it 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. Rainbow connection has an interesting application for the secure communication in networks. 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\H{o}s-Gallai type results for $rc(G).$ \end{abstract}


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors