The rainbow connection number of 2-connected graphs

Ingo Schiermeyer; Jan Ekstein; Maria Koch; P\v{r}emysl Holub; Stephan Matos Camacho; Tom\'a\v{s} Kaiser; Zden\v{e}k Ryj\'a\v{c}ek

arxiv: 1110.5736 · v1 · pith:53JVP26Znew · submitted 2011-10-26 · 🧮 math.CO

The rainbow connection number of 2-connected graphs

Jan Ekstein , P\v{r}emysl Holub , Tom\'a\v{s} Kaiser , Maria Koch , Stephan Matos Camacho , Zden\v{e}k Ryj\'a\v{c}ek , Ingo Schiermeyer This is my paper

classification 🧮 math.CO

keywords numberconnectionrainbowconnectedeverygraphverticesbound

0 comments

read the original abstract

The rainbow connection number of a graph G is the least number of colours in a (not necessarily proper) edge-colouring of G such that every two vertices are joined by a path which contains no colour twice. Improving a result of Caro et al., we prove that the rainbow connection number of every 2-connected graph with n vertices is at most the ceiling of n/2. The bound is optimal.

This paper has not been read by Pith yet.

The rainbow connection number of 2-connected graphs

discussion (0)