Geodesic
Kernels by Monochromatic Paths and Color-Perfect Digraphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 309-321

Voir la notice de l'article provenant de la source Library of Science

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 C(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 C(D) is not strong, then D has an mp-kernel. Previous interesting results are generalized, as for example Richardson′s Theorem.
Keywords: kernel, kernel perfect digraph, kernel by monochromatic paths, color-class digraph, quasi color-perfect digraph, color-perfect digraph 
@article{DMGT_2016_36_2_a4,
     author = {Galeana-\'Sanchez, Hortensia and S\'anchez-L\'opez, Roc{\'\i}o},
     title = {Kernels by {Monochromatic} {Paths} and {Color-Perfect} {Digraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {309--321},
     publisher = {mathdoc},
     volume = {36},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a4/}
}
TY  - JOUR
AU  - Galeana-Śanchez, Hortensia
AU  - Sánchez-López, Rocío
TI  - Kernels by Monochromatic Paths and Color-Perfect Digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 309
EP  - 321
VL  - 36
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a4/
LA  - en
ID  - DMGT_2016_36_2_a4
ER  - 
%0 Journal Article
%A Galeana-Śanchez, Hortensia
%A Sánchez-López, Rocío
%T Kernels by Monochromatic Paths and Color-Perfect Digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 309-321
%V 36
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a4/
%G en
%F DMGT_2016_36_2_a4
Galeana-Śanchez, Hortensia; Sánchez-López, Rocío. Kernels by Monochromatic Paths and Color-Perfect Digraphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 309-321. http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a4/