Přejít k obsahu


Rainbow connection and forbidden subgraphs

Citace:
HOLUB, P., RYJÁČEK, Z., SCHIERMEYER, I., VRÁNA, P. Rainbow connection and forbidden subgraphs. DISCRETE MATHEMATICS, 2015, roč. 338, č. 10, s. 1706-1713. ISSN: 0012-365X
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: Rainbow connection and forbidden subgraphs
Rok vydání: 2015
Autoři: RNDr. Přemysl Holub Ph.D. , Prof. RNDr. Zdeněk Ryjáček DrSc. , Prof. Dr. Ingo Schiermeyer , Mgr. Petr Vrána Ph.D. ,
Abstrakt CZ: Souvislý hranově obarvený graf G se nazývá duhově souvislý, jestliže každé dva vrcholy grafu G jsou spojeny cestou, jejíž hrany mají navzájem různé barvy. Číslo duhové souvislosti rc(G) je rovno minimálnímu počtu barev potřebných k tomu, aby graf G byl duhově souvislý. V tomto článku se autoři zabývají třídami F souvislých podgrafů, pro něž existuje konstanta k taková, že každý graf bez F má rc(G)?diam(G)+k, kde diam (G) značí průměr grafu. Zde je kompletně vyřešena tato otázka pro |F|=1 a |F|=2.
Abstrakt EN: 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 needed to make G rainbow-connected. We consider families F of connected graphs for which there is a constant k such that, for every connected F-free graph G, rc(G)?diam(G)+k, where diam(G) is the diameter of G. In this paper, we give a complete answer for |F|=1 and |F|=2.
Klíčová slova

Zpět

Patička