Heredity properties of connectedness in edge-coloured complete graphs

• Autorzy: Idzik A. , Tuza Z.

Warianty tytułu

PL

Dziedziczne własności spójności w krawędziowo pokolorowanych grafach zupełnych

• Języki publikacji: EN

Abstrakty

EN

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.

PL

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.

Słowa kluczowe

EN

complete graph; connected graph; edge colouring; 3-uniform hypergraph

PL

grafy zupełne

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 1999
• Tom: nr 876
• Strony: 3--12

Twórcy

autor

Idzik A.

autor

Tuza Z.

• Institute of Computer Science Polish Academy of Sciences 21 Ordona St. 01-237 Warszawa, Poland,