Přejít k obsahu
﻿

### On forbidden subgraphs and rainbow connection of graphs with minimum degree 2

 Citace: HOLUB, P., RYJÁČEK, Z., SCHIERMEYER, I. On forbidden subgraphs and rainbow connection of graphs with minimum degree 2. DISCRETE MATHEMATICS, 2015, roč. 338, č. 3, s. 1-8. ISSN: 0012-365X ČLÁNEK eng On forbidden subgraphs and rainbow connection of graphs with minimum degree 2 2015 RNDr. Přemysl Holub Ph.D. , Prof. RNDr. Zdeněk Ryjáček DrSc. , Prof. Ingo Schiermeyer Ph.D. Souvislý hranově obarvený graf $G$ nazveme duhově souvislý, jestliže každé dva vrcholy $G$ jsou spojeny cestou, jejiž hrany mají navzájem různé barvy; číslo duhové souvislosti $rc(G)$ grafu $G$ je minimální počet barev potřebných k tomu, aby $G$ byl duhově souvislý. V tomto článku uvažujeme třídy souvislých grafů $\cF$, pro které existuje konstanta $K_\cF$ taková, že pro každý souvislý graf bez $\cF$ s minimálním stupněm 2 je $rc(G) \leq \diam(G)+k_\cF$, kde $\diam(G)$ je průměr grafu. V tomto článku kompletně řešíme tento problém pro třídy $\cF$ s jedním a dvěma grafy. A connected edge-colored graph $G$ is rainbow-connected if any two distinct vertices of $G$ are connected by a path whose edges have pairwise distinct colors; the rainbow connection number $\rc(G)$ of $G$ is the minimum number of colors such that $G$ is rainbow-connected. We consider families $\cF$ of connected graphs for which there is a constant $k_\cF$ such that, for every connected $\cF$-free graph $G$ with minimum degree two, $\rc(G)\leq\diam(G)+k_\cF$, where $\diam(G)$ is the diameter of $G$. In the paper, we give a complete answer for $|\cF|\in \{1,2\}$.

Zpět