Přejít k obsahu
﻿

### The rainbow connection number of 2-connected graphs

 Citace: [] HOLUB, P. The rainbow connection number of 2-connected graphs. 2011. PŘEDNÁŠKA, POSTER eng The rainbow connection number of 2-connected graphs 2011 RNDr. Přemysl Holub Ph.D. Hranově obarvený graf G je duhově souvislý, jestliže každé dva vrcholy grafu G jsou spojeny cestou, jejíž hrany mají různé barvy. Číslo duhové souvislosti souvislého grafu G, značíme rc(G), je nejmenší počet barev potřebných k tomu, aby daný graf byl duhově souvislý. Caro a kol. ukázali, že pro 2-souvislé grafy na n vrcholech je rc(G) nejvýše n/2 + O(sqrt(n)). V této práci ukážeme, že pro 2-souvislé grafy platí rc(G) <= n/2+1. An edge-coloured graph $G$ is rainbow connected if any two vertices are connected by a path whose edges have different colours. 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. Caro et al. showed that, for a $2$-connected graph $G$ of order $n$, $rc(G)\leq \frac n2 + O(\sqrt{n})$. In this paper we prove that $rc(G)\leq \frac n2+1$ for any $2$-connected graph $G$.

Zpět