Kernels by Monochromatic Directed Paths in $m$-Colored Digraphs with Quasi-Transitive Chromatic Classes

Abstract

In this paper, we give sufficient conditions for the existence of kernels by monochromatic directed paths (m.d.p.) in digraphs with quasi-transitive colorings. Let $D$ be an $m$-colored digraph. We prove that if every chromatic class of $D$ is quasi-transitive, every cycle is quasi-transitive in the rim and $D$ does not contain polychromatic triangles, then $D$ has a kernel by m.d.p. The same result is valid if we preserve the first two conditions before and replace the last one by: there exists $k\ge 4$ such that every ${\overrightarrow{C}}_k$ is quasi-monochromatic and every ${\overrightarrow{C}}_{k-1}$ ($3\le l\le k-1$) is not polychromatic. Finally, we also show that if every chromatic class of $D$ is quasi-transitive, every cycle in $D$ induces a quasi-transitive digraph and $D$ does not contain polychromatic ${\overrightarrow{C}}_3$, then $D$ has a kernel by m.d.p. Some corollaries are obtained for the existence of kernels by m.d.p. in $m$-colored tournaments.