γ-CYCLES IN ARC-COLORED DIGRAPHS

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 subset of V(D) is said to be a kernel by monochromatic paths of D if it satisfies the two following conditions: (i) for every pair of different vertices u, v is an element of N there is no monochromatic path in D between them, and (ii) for every vertex x is an element of V(D) - N there is a vertex y is an element of N such that there is an xy-monochromatic path in D. A gamma-cycle in D is a sequence of different vertices gamma = (u(0), u(1), ..., u(n), u(0)) such that for every i is an element of {0, 1, ..., n}: (i) there is a u(i)u(i+1)-monochromatic path, and (ii) there is no u(i+1)u(i)-monochromatic path. The addition over the indices of the vertices of gamma is taken modulo (n + 1). If D is an m-colored digraph, then the closure of D, denoted by e(D), is the m-colored multidigraph defined as follows: V(e(D)) = V(D), A(e(D)) = A(D) U {(u, v) with color i vertical bar 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 boolean OR C-2 of the set of colors of D such that: (1) D[(C) over cap (i)] (the subdigraph spanned by the arcs with colors in C-i) contains no gamma-cycles for i is an element of {1, 2}; (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) is an element of A(e(D)) or (z, x(0)) E A(e(D)); (3) 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), (xo, u), (u, xo), (xo, 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 gamma-cycles. Generalizations of many previous results are obtained as a direct consequence of this theorem.