Přejít k obsahu


Finite families of forbidden subgraphs for rainbow connection in graphs

Citace:
BROUSEK, J., HOLUB, P., RYJÁČEK, Z., VRÁNA, P. Finite families of forbidden subgraphs for rainbow connection in graphs. DISCRETE MATHEMATICS, 2016, roč. 339, č. 9, s. 2304-2312. ISSN: 0012-365X
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: Finite families of forbidden subgraphs for rainbow connection in graphs
Rok vydání: 2016
Autoři: RNDr. Jan Brousek Ph.D. , RNDr. Přemysl Holub Ph.D. , Prof. RNDr. Zdeněk Ryjáček DrSc. , Mgr. Petr Vrána Ph.D. ,
Abstrakt CZ: Souvislý hranově obarvený graf G je duhově souvislý, jestliže každé dva jeho různé vrcholy jsou spojeny cestou, jejíž hrany mají vesměs různé barvy, a číslo duhové souvislosti rc(G) grafu G je nejmenší počet barev obarvení, při kterém je G duhově souvislý. Zkoumáme množiny F souvislých grafů, pro které existuje konstanta k taková, že pro každý souvislý graf G, neobsahující indukovaný podgraf z F, je rc(G) nejvýše diam(G)+k, kde diam(G) je průměr G. V článku finalizujeme naše předchozí výsledky a dáváme úplnou odpověď pro každou konečnou množinu F.
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 such that G is 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) is at most diam(G)+k, where diam(G) is the diameter of G. In the paper, we finalize our previous considerations and give a complete answer for any finite family F.
Klíčová slova

Zpět

Patička