ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory  18(1) (1998)   91-98
DOI: 10.7151/dmgt.1066


H. Galeana-Sánchez

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 Ciencias
de la Universidad Nacional Autónoma de México
México, D.F.


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).

Keywords: kernel, kernel by monochromatic paths, line digraph, edge coloured digraph.

1991 Mathematics Subject Classification: 05C20.


[1] C. Berge, Graphs (North Holland, Amsterdam, New York, 1985).
[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.
[3] H. Galeana-Sánchez and J.J. García Ruvalcaba, Kernels in { C3, T3}-free arc colorations of Kn-e, submitted.
[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.
[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.

Received 27 April 1997
Revised 22 September 1997