Cycles and transitivity by monochromatic paths in arc-coloured digraphs

摘要

A digraph D is an m - coloured digraph if its arcs are coloured with m colours. If D is an m -coloured digraph and a ∈ A ( D ) , then c o l o u r ( a ) will denote the colour has been used on a . A path (or a cycle) is monochromatic if all of its arcs are coloured alike. A set N ? V ( D ) is 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 x y -monochromatic path. The closure of D , denoted by C ( D ) , is the m -coloured multidigraph defined as follows: V ( C ( D ) ) = V ( D ) , A ( C ( D ) ) = A ( D ) ∪ { ( u , v ) with colour i | there is an u v -path coloured i contained in D } . A subdigraph H in D is rainbow if all of its arcs have different colours. A digraph D is transitive by monochromatic paths if the existence of an x y -monochromatic path and an y z -monochromatic path in D imply that there is an x z -monochromatic path in D . We will denote by P 3 ? the path of length 3 and by C 3 ? the cycle of length 3. Let D be a finite m -coloured digraph. Suppose that C is the set of colours used in A ( D ) , and ζ = { C 1 , C 2 , … , C k } ( k ≥ 2 ) is a partition of C , such that for every i ∈ { 1 , 2 , … , k } happens that H i = D [ { a ∈ A ( D ) ∣ c o l o u r ( a ) ∈ C i } ] is transitive by monochromatic paths. Let { ζ 1 , ζ 2 } be a partition of ζ , and D i will be the spanning subdigraph of D such that A ( D i ) = { a ∈ A ( D ) ∣ c o l o u r ( a ) ∈ C j f o r s o m e C j ∈ ζ i } . 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 D is a finite m -coloured digraph that admits a partition { C 1 , C 2 } of the set of colours of D such that for each i ∈ { 1 , 2 } every cycle in the subdigraph D [ C i ] spanned by the arcs with colours in C i is monochromatic, C ( D ) does not contain neither rainbow triangles nor rainbow P 3 ? ( path of length 3) involving colours of both C 1 and C 2 ; then D has a kernel by monochromatic paths.