Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

1 1999

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: grafy zupełne

Sortuj według:

Ogranicz wyniki do:

Heredity properties of connectedness in edge-coloured complete graphs

Idzik A., Tuza Z.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

1999

nr 876

3-12

If the monochromatic graphs G1 and G2 in a 2-edge-coloured complete graph Km(m>6) are connected, then there exist at least two vertices x such that the graphs G1\x and G2\x are also connected. Similar theorems are proved for k-edge-coloured complete graphs. They generalize earlier results of Idzik, Komar and Malawski (Discrete Math. 66(1987), 119-125). Examples are shown that analogous theorems are no longer true for 3-uniform complete hypergraphs.

Jeśli monochormatyczne grafy G1 i G2 w 2-krawędziowo pokolorowanym grafie zupełnym Km(m>6) są spójne, to istnieją co najmniej dwa wierzchołki x takie, że grafy G1\x i G2\x są również spójne. Podobne twierdzenia są udowodnione dla k-krawędziowo pokolorowanych grafów zupełnych. Twierdzenia te uogólniają wcześniejsze rezultaty Idzika, Komara i Malawskiego (Discrete Math. 66 (1987), 119-125). Sa pokazane przykłady, że analogiczne twierdzenia nie są prawdziwe dla 3-jednostajnych hipergrafów zupełnych.