PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 2 | 309-321
Tytuł artykułu

Kernels by Monochromatic Paths and Color-Perfect Digraphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
For a digraph D, V (D) and A(D) will denote the sets of vertices and arcs of D respectively. In an arc-colored digraph, a subset K of V(D) is said to be kernel by monochromatic paths (mp-kernel) if (1) for any two different vertices x, y in N there is no monochromatic directed path between them (N is mp-independent) and (2) for each vertex u in V (D) \ N there exists v ∈ N such that there is a monochromatic directed path from u to v in D (N is mp-absorbent). If every arc in D has a different color, then a kernel by monochromatic paths is said to be a kernel. Two associated digraphs to an arc-colored digraph are the closure and the color-class digraph CC(D). In this paper we will approach an mp-kernel via the closure of induced subdigraphs of D which have the property of having few colors in their arcs with respect to D. We will introduce the concept of color-perfect digraph and we are going to prove that if D is an arc-colored digraph such that D is a quasi color-perfect digraph and CC(D) is not strong, then D has an mp-kernel. Previous interesting results are generalized, as for example Richardson′s Theorem.
Wydawca
Rocznik
Tom
36
Numer
2
Strony
309-321
Opis fizyczny
Daty
wydano
2016-05-01
otrzymano
2014-08-18
poprawiono
2015-06-23
zaakceptowano
2015-06-23
online
2016-04-15
Twórcy
  • Instituto de Matemáticas UNAM, Ciudad Universitaria Circuito Exterior 04510, México, D.F., México, hgaleana@matem.unam.mx
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1860
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.