Kernels by monochromatic paths in digraphs with covering number 2

Abstract

We call the digraph D an k-colored digraph if the arcs of D are colored with k colors. A subdigraph H of D is called monochromatic if all of its arcs are colored alike. A set N ⊆ V(D) is said to be 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 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. In this paper, we prove that if D is an k-colored digraph that can be partitioned into two vertex-disjoint transitive tournaments such that every directed cycle of length 3, 4 or 5 is monochromatic, then D has a kernel by monochromatic paths. This result gives a positive answer (for this family of digraphs) of the following question, which has motivated many results in monochromatic kernel theory: Is there a natural number l such that if a digraph D is k-colored so that every directed cycle of length at most l is monochromatic, then D has a kernel by monochromatic paths?