γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs
Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 3, p. 493.

Voir la notice de l'article dans European Digital Mathematics Library

We call the digraph D an m-coloured digraph if its arcs are coloured with m colours. If D is an m-coloured digraph and a ∈ A(D), colour(a) will denote the colour has been used on a. A path (or a cycle) is called monochromatic if all of its arcs are coloured alike. A γ-cycle in D is a sequence of vertices, say γ = (u0, u1, . . . , un), such that ui ≠ uj if i ≠ j and for every i ∈ 0, 1, . . . , n there is a uiui+1-monochromatic path in D and there is no ui+1ui-monochromatic path in D (the indices of the vertices will be taken mod n+1). A set N ⊆ V (D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u, v ∈ N there is no monochromatic path between them and; (ii) for every vertex x ∈ V (D) N there is a vertex y ∈ N such that there is an xy-monochromatic path. Let D be a finite m-coloured digraph. Suppose that C1,C2 is a partition of C, the set of colours of D, and Di will be the spanning subdigraph of D such that A(Di) = a ∈ A(D) | colour(a) ∈ Ci. In this paper, we give some sufficient conditions for the existence of a kernel by monochromatic paths in a digraph with the structure mentioned above. In particular we obtain an extension of the original result by B. Sands, N. Sauer and R. Woodrow that asserts: Every 2-coloured digraph has a kernel by monochromatic paths. Also, we extend other results obtained before where it is proved that under some conditions an m-coloured digraph has no γ-cycles.
Classification : 05C15, 05C20, 05C38, 05C69
Mots-clés : digraph, kernel, kernel by monochromatic paths, γ-cycle, -cycle
@article{DMGT_2013__33_3_268248,
     author = {Enrique Casas-Bautista and Hortensia Galeana-S\'anchez and Roc{\'\i}o Rojas-Monroy},
     title = {\ensuremath{\gamma}-Cycles {And} {Transitivity} {By} {Monochromatic} {Paths} {In} {Arc-Coloured} {Digraphs}},
     journal = {Discussiones Mathematicae Graph Theory},
     pages = {493},
     publisher = {mathdoc},
     volume = {33},
     number = {3},
     year = {2013},
     zbl = {1275.05025},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_268248/}
}
TY  - JOUR
AU  - Enrique Casas-Bautista
AU  - Hortensia Galeana-Sánchez
AU  - Rocío Rojas-Monroy
TI  - γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs
JO  - Discussiones Mathematicae Graph Theory
PY  - 2013
SP  - 493
VL  - 33
IS  - 3
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_268248/
LA  - en
ID  - DMGT_2013__33_3_268248
ER  - 
%0 Journal Article
%A Enrique Casas-Bautista
%A Hortensia Galeana-Sánchez
%A Rocío Rojas-Monroy
%T γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs
%J Discussiones Mathematicae Graph Theory
%D 2013
%P 493
%V 33
%N 3
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_268248/
%G en
%F DMGT_2013__33_3_268248
Enrique Casas-Bautista; Hortensia Galeana-Sánchez; Rocío Rojas-Monroy. γ-Cycles And Transitivity By Monochromatic Paths In Arc-Coloured Digraphs. Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 3, p. 493. https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_268248/