Geodesic
Kernels and cycles' subdivisions in arc-colored tournaments
Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 1, pp. 101-117

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

Let D be a digraph. D is said to be an m-colored digraph if the arcs of D are colored with m colors. A path P in D is called monochromatic if all of its arcs are colored alike. Let D be an m-colored digraph. A set N ⊆ V(D) is said to be a kernel by monochromatic paths of D if it satisfies the following conditions: a) for every pair of different vertices u,v ∈ N there is no monochromatic directed path between them; and b) for every vertex x ∈ V(D)-N there is a vertex n ∈ N such that there is an xn-monochromatic directed path in D. In this paper we prove that if T is an arc-colored tournament which does not contain certain subdivisions of cycles then it possesses a kernel by monochromatic paths. These results generalize a well known sufficient condition for the existence of a kernel by monochromatic paths obtained by Shen Minggang in 1988 and another one obtained by Hahn et al. in 2004. Some open problems are proposed.
Keywords: kernel, kernel by monochromatic paths, tournament 
@article{DMGT_2009_29_1_a6,
     author = {Delgado-Escalante, Pietra and Galeana-S\'anchez, Hortensia},
     title = {Kernels and cycles' subdivisions in arc-colored tournaments},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {101--117},
     publisher = {mathdoc},
     volume = {29},
     number = {1},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2009_29_1_a6/}
}
TY  - JOUR
AU  - Delgado-Escalante, Pietra
AU  - Galeana-Sánchez, Hortensia
TI  - Kernels and cycles' subdivisions in arc-colored tournaments
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2009
SP  - 101
EP  - 117
VL  - 29
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2009_29_1_a6/
LA  - en
ID  - DMGT_2009_29_1_a6
ER  - 
%0 Journal Article
%A Delgado-Escalante, Pietra
%A Galeana-Sánchez, Hortensia
%T Kernels and cycles' subdivisions in arc-colored tournaments
%J Discussiones Mathematicae. Graph Theory
%D 2009
%P 101-117
%V 29
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2009_29_1_a6/
%G en
%F DMGT_2009_29_1_a6
Delgado-Escalante, Pietra; Galeana-Sánchez, Hortensia. Kernels and cycles' subdivisions in arc-colored tournaments. Discussiones Mathematicae. Graph Theory, Tome 29 (2009) no. 1, pp. 101-117. http://geodesic.mathdoc.fr/item/DMGT_2009_29_1_a6/