Geodesic
Monochromatic paths and monochromatic sets of arcs in quasi-transitive digraphs
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 4, pp. 545-553

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

Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively. We call the digraph D an m-coloured digraph if each arc of D is coloured by an element of 1,2,...,m where m ≥ 1. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if there is no monochromatic path between two vertices of N and if for every vertex v not in N there is a monochromatic path from v to some vertex in N. A digraph D is called a quasi-transitive digraph if (u,v) ∈ A(D) and (v,w) ∈ A(D) implies (u,w) ∈ A(D) or (w,u) ∈ A(D). We prove that if D is an m-coloured quasi-transitive digraph such that for every vertex u of D the set of arcs that have u as initial end point is monochromatic and D contains no C₃ (the 3-coloured directed cycle of length 3), then D has a kernel by monochromatic paths.
Keywords: m-coloured quasi-transitive digraph, kernel by monochromatic paths 
@article{DMGT_2010_30_4_a1,
     author = {Galeana-S\'anchez, Hortensia and Rojas-Monroy, R. and Zavala, B.},
     title = {Monochromatic paths and monochromatic sets of arcs in quasi-transitive digraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {545--553},
     publisher = {mathdoc},
     volume = {30},
     number = {4},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a1/}
}
TY  - JOUR
AU  - Galeana-Sánchez, Hortensia
AU  - Rojas-Monroy, R.
AU  - Zavala, B.
TI  - Monochromatic paths and monochromatic sets of arcs in quasi-transitive digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 545
EP  - 553
VL  - 30
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a1/
LA  - en
ID  - DMGT_2010_30_4_a1
ER  - 
%0 Journal Article
%A Galeana-Sánchez, Hortensia
%A Rojas-Monroy, R.
%A Zavala, B.
%T Monochromatic paths and monochromatic sets of arcs in quasi-transitive digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 545-553
%V 30
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a1/
%G en
%F DMGT_2010_30_4_a1
Galeana-Sánchez, Hortensia; Rojas-Monroy, R.; Zavala, B. Monochromatic paths and monochromatic sets of arcs in quasi-transitive digraphs. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 4, pp. 545-553. http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a1/