PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Discussiones Mathematicae Graph Theory

2000 | 20 | 2 | 243-254
Tytuł artykułu

### Kernels in the closure of coloured digraphs

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Let D be a digraph with V(D) and A(D) the sets of vertices and arcs of D, respectively. A kernel of D is a set I ⊂ V(D) such that no arc of D joins two vertices of I and for each x ∈ V(D)∖I there is a vertex y ∈ I such that (x,y) ∈ A(D). A digraph is kernel-perfect if every non-empty induced subdigraph of D has a kernel. If D is edge coloured, we define the closure ξ(D) of D the multidigraph with V(ξ(D)) = V(D) and $A(ξ(D)) = ⋃_i{(u,v)$ with colour i there exists a monochromatic path of colour i from the vertex u to the vertex v contained in D}.
Let T₃ and C₃ denote the transitive tournament of order 3 and the 3-cycle, respectively, both of whose arcs are coloured with 3 different colours. In this paper, we survey sufficient conditions for the existence of kernels in the closure of edge coloured digraphs, also we prove that if D is obtained from an edge coloured tournament by deleting one arc and D does not contain T₃ or C₃, then ξ(D) is a kernel-perfect digraph.
Słowa kluczowe
EN
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
243-254
Opis fizyczny
Daty
wydano
2000
otrzymano
2000-01-31
poprawiono
2000-10-02
Twórcy
• Instituto de Matemáticas, UNAM, Circuito Exterior, 04510 México, D.F. México