Přejít k obsahu


Rainbow cycles in edge-colored graphs

Citace:
ČADA, R., KANEKO, A., RYJÁČEK, Z., YOSHIMOTO, K. Rainbow cycles in edge-colored graphs. DISCRETE MATHEMATICS, 2016, roč. 339, č. 4, s. 1387-1392. ISSN: 0012-365X
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: Rainbow cycles in edge-colored graphs
Rok vydání: 2016
Autoři: Doc. Ing. Roman Čada Ph.D. , Atsushi Kaneko , Prof. RNDr. Zdeněk Ryjáček DrSc. , Prof. Kiyoshi Yoshimoto PhD
Abstrakt CZ: Je-li G hranově obarvený graf, pak minimální barevný stupeň grafu G je největší přirozené číslo k takové, že každý vrchol grafu G je incidentní s alespoň k hranami majícími různé barvy. Podgraf F grafu G je duhová, jestliže žádné dvě jeho hrany nemají stejnou barvu. V článku dáváme podmínky na minimální barevný stupeň, který zaručuje existenci (i) duhové kružnice délky 4 v grafu bez trojúhelníků, a (ii) duhové kružnice délky alespoň 4 v grafu.
Abstrakt EN: Let G be a graph with an edge coloring. The minimum color degree of G is the largest integer k such that each vertex of G is incident with at least k edges having pairwise distinct colors. A subgraph F of G is rainbow if all edges of F have pairwise distinct colors. In the paper, we give a minimum color degree condition that guarantees the existence of a (i) rainbow 4-cycle in a triangle-free graph, and (ii) of a rainbow cycle of length at least 4 in a graph.
Klíčová slova

Zpět

Patička