19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Rainbow numbers and rainbow connection
Presented by Prof. Ingo SCHIERMEYER
Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs
Content
\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}
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled