We call a digraph D an m -colored digraph if the arcs of D are colored with m colors. A directed path (or a directed cycle) is called monochromatic if all of its arcs are colored alike. A subdigraph H in D is called rainbow if all of its arcs have different colors. A set N ? V ( D ) is said to be a kernel by monochromatic paths of D if it satisfies the two following conditions:for every pair of different vertices u, v ∈ N there is no monochromatic path in D between them, andfor every vertex x ∈ V ( D ) ? N there is a vertex y ∈ N such that there is an xy -monochromatic path in D .A γ -cycle in D is a sequence of different vertices γ = ( u _(0), u _(1), . . , u_(n), u _(0)) such that for every i ∈ {0, 1, . . , n }:there is a u_(i)u _(i+1)-monochromatic path, andthere is no u _( i +1) u_(i) -monochromatic path.The addition over the indices of the vertices of γ is taken modulo ( n + 1). If D is an m -colored digraph, then the closure of D , denoted by ?( D ), is the m -colored multidigraph defined as follows: V (? ( D )) = V ( D ), A (? ( D )) = A ( D ) ∪ {( u, v ) with color i | there exists a uv -monochromatic path colored i contained in D }.In this work, we prove the following result. Let D be a finite m -colored digraph which satisfies that there is a partition C = C _(1) ∪ C _(2) of the set of colors of D such that: D [?_( i )] (the subdigraph spanned by the arcs with colors in C_(i) ) contains no γ -cycles for i ∈ {1, 2};If ? ( D ) contains a rainbow C _(3) = ( x _(0), z, w, x _(0)) involving colors of C _(1) and C _(2), then ( x _(0), w ) ∈ A (? ( D )) or ( z, x _(0)) ∈ A (? ( D ));If ? ( D ) contains a rainbow P _(3) = ( u, z, w, x _(0)) involving colors of C _(1) and C _(2), then at least one of the following pairs of vertices is an arc in ? ( D ): ( u, w ), ( w, u ), ( x _(0), u ), ( u, x _(0)), ( x _(0), w ), ( z, u ), ( z, x _(0)).Then D has a kernel by monochromatic paths.This theorem can be applied to all those digraphs that contain no γ- cycles. Generalizations of many previous results are obtained as a direct consequence of this theorem.
展开▼
