Přejít k obsahu


Forbidden subgraphs for rainbow connection

Citace:
BROUSEK, J., HOLUB, P., RYJÁČEK, Z., VRÁNA, P. Forbidden subgraphs for rainbow connection. Nový Smokovec, Slovensko, 2014.
Druh: PŘEDNÁŠKA, POSTER
Jazyk publikace: eng
Anglický název: Forbidden subgraphs for rainbow connection
Rok vydání: 2014
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 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, and 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 talk, we give a complete answer for any finite family F.
Klíčová slova

Zpět

Patička