Přejít k obsahu


The rainbow connection number of 2-connected graphs

Citace:
EKSTEIN, J., HOLUB, P., KAISER, T., KOCH, M., MATOS CAMACHO, S., RYJÁČEK, Z., SCHIERMEYER, I. The rainbow connection number of 2-connected graphs. DISCRETE MATHEMATICS, 2013, roč. 313, č. 19, s. 1884-1892. ISSN: 0012-365X
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: The rainbow connection number of 2-connected graphs
Rok vydání: 2013
Autoři: RNDr. Jan Ekstein Ph.D. , RNDr. Přemysl Holub Ph.D. , Doc. RNDr. Tomáš Kaiser Ph.D. , Dr. Maria Koch , Dr. Stephan Matos Camacho , Prof. RNDr. Zdeněk Ryjáček DrSc. , Prof. Dr. Ingo Schiermeyer
Abstrakt CZ: Číslo duhové souvislosti grafu G je nejmenší počet barev v (ne nutně přípustném) hranovém obarvení grafu G takovém, že každé dva uzly jsou spojeny cestou, která neobsahuje žádnou barvu dvakrát. V článku dokazujeme, že číslo duhové souvislosti každého 2-souvislého grafu na n uzlech je nejvýše horní celá část n/2. Tato horní hranice je nejlepší možná.
Abstrakt EN: The rainbow connection number of a graph G is the least number of colours in a (not necessarily proper) edge-colouring of G such that every two vertices are joined by a path which contains no colour twice. In the paper we prove that the rainbow connection number of every 2-connected graph with n vertices is at most the upper integer part of n/2. The bound is optimal.
Klíčová slova

Zpět

Patička