We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the two following conditions (i) for every pair of different vertices u, v ∈ N there is no monochromatic directed 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 directed path. Let D be an m-coloured digraph and L(D) its line digraph. The inner m-coloration of L(D) is the edge coloration of L(D) defined as follows: If h is an arc of D of colour c, then any arc of the form (x,h) in L(D) also has colour c. In this paper it is proved that if D is an m-coloured digraph without monochromatic directed cycles, then the number of kernels by monochromatic paths in D is equal to the number of kernels by monochromatic paths in the inner edge coloration of L(D).
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1066,
author = {H. Galeana-S\'anchez and L. Pastrana Ram\'\i rez},
title = {Kernels in edge coloured line digraph},
journal = {Discussiones Mathematicae Graph Theory},
volume = {18},
year = {1998},
pages = {91-98},
zbl = {0913.05048},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1066}
}
H. Galeana-Sánchez; L. Pastrana Ramírez. Kernels in edge coloured line digraph. Discussiones Mathematicae Graph Theory, Tome 18 (1998) pp. 91-98. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1066/
[000] [1] C. Berge, Graphs (North Holland, Amsterdam, New York, 1985).
[001] [2] H. Galeana-Sánchez, On monochromatic paths and monochromatic cycles in edge coloured tournaments, Discrete Math. 156 (1996) 103-112, doi: 10.1016/0012-365X(95)00036-V. | Zbl 0857.05054
[002] [3] H. Galeana-Sánchez and J.J. García Ruvalcaba, Kernels in {C₃, T₃}-free arc colorations of Kₙ - e, submitted. | Zbl 0990.05060
[003] [4] B. Sands, N. Sauer and R. Woodrow, On Monochromatic Paths in Edge Coloured Digraphs, J. Combin. Theory (B) 33 (1982) 271-275, doi: 10.1016/0095-8956(82)90047-8. | Zbl 0488.05036
[004] [5] Shen Minggang, On Monochromatic Paths in m-Coloured Tournaments, J. Combin. Theory (B) 45 (1988) 108-111, doi: 10.1016/0095-8956(88)90059-7. | Zbl 0654.05033