ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Graph Theory 18(1) (1998) 91-98DOI: 10.7151/dmgt.1066
Instituto de Matemáticas, U.N.A.M., C.U.
Circuito Exterior, D. F. 04510 México
L. Pastrana Ramírez
Departamento de Matemáticas de la Facultad de
de la Universidad Nacional Autónoma de México
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
Keywords: kernel, kernel by monochromatic paths, line digraph, edge coloured
1991 Mathematics Subject Classification: 05C20.
Received 27 April 1997
Revised 22 September 1997