Přejít k obsahu

Rainbow connection and forbidden induced subgraphs

HOLUB, P., RYJÁČEK, Z., SCHIERMEYER, I., VRÁNA, P. Rainbow connection and forbidden induced subgraphs. Ilmenau, Germany, 2015.
Jazyk publikace: eng
Anglický název: Rainbow connection and forbidden induced subgraphs
Rok vydání: 2015
Autoři: RNDr. Přemysl Holub Ph.D. , Prof. RNDr. Zdeněk Ryjáček DrSc. , Prof. Dr. rer. nat. habil. Ingo Schiermeyer , 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; 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_F such that, for every connected F-free graph G, rc(G)<= diam(G)+k_F, where diam(G) is the diameter of G. In this talk, we give a complete answer for |\cF|\in \{1,2\} in general graphs and in graphs with minimum degree 2, respectively.
Klíčová slova