Cycles and transitivity by monochromatic paths in arc-coloured digraphs

• Published in: AKCE International Journal of Graphs and Combinatorics 2015-11, Vol.12 (2-3), p.104-112
• Main Authors: Casas-Bautista, Enrique, Galeana-Sánchez, Hortensia, Rojas-Monroy, Rocío
• Format: Article
• Language: English
• Subjects: Cycle; Digraph; Kernel; Kernel by monochromatic paths; Transitivity by monochromatic paths
• ISSN: 0972-8600; 2543-3474
• DOI: 10.1016/j.akcej.2015.11.003

A digraph is an -coloured digraph if its arcs are coloured with colours. If is an -coloured digraph and , then will denote the colour has been used on . A path (or a cycle) is monochromatic if all of its arcs are coloured alike. A set is a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices there is no monochromatic path between them and; (ii) for every vertex there is a vertex such that there is an -monochromatic path. The closure of , denoted by , is the -coloured multidigraph defined as follows: , with colour there is an -path coloured contained in . A subdigraph in is rainbow if all of its arcs have different colours. A digraph is transitive by monochromatic paths if the existence of an -monochromatic path and an -monochromatic path in imply that there is an -monochromatic path in . We will denote by the path of length 3 and by the cycle of length 3. Let be a finite -coloured digraph. Suppose that is the set of colours used in , and ( ) is a partition of , such that for every happens that is transitive by monochromatic paths. Let be a partition of , and will be the spanning subdigraph of such that . 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 extensions of the following two original results: The result by Sands et al. (1982) that asserts: Every 2-coloured digraph has a kernel by monochromatic paths, and the result by Galeana-Sánchez et al. (2011) that asserts: If is a finite -coloured digraph that admits a partition of the set of colours of such that for each every cycle in the subdigraph spanned by the arcs with colours in is monochromatic, does not contain neither rainbow triangles nor rainbow (path of length 3) involving colours of both and ; then has a kernel by monochromatic paths.