Richardson’s Theorem for kk-colored kernels in strongly connected digraphs

A digraph D=(V,A)D=(V,A) is said to be mm-colored   if its arcs are colored with mm colors. An mm-colored digraph DD has a kk-colored kernel   if there exists K⊆VK⊆V such that (i) for every v∈V∖Kv∈V∖K there exist a qq-colored directed path, with q≤kq≤k, from vv to a vertex of KK, and (ii) for every pair {u,v}⊆K{u,v}⊆K every directed path from uu to vv uses at least k+1k+1 colors.Given an mm-colored digraph DD, the color-class digraph   of DD, denoted C(D), is defined as follows: the vertices of C(D) are the mm colors of DD, and (i,j)(i,j) is an arc of C(D) if and only if there exist two consecutive arcs in DD, namely (u,v)(u,v) and (v,w)(v,w), such that (u,v)(u,v) has color ii and (v,w)(v,w) has color jj.A digraph DD is said to be cyclically  kk-partite   if there is a partition {Vi}i=0k−1 of its vertices in independent sets such that every arc in DD is either a loop or a ViVi+1ViVi+1-arc (taken the index modulo kk). In Galeana-Sánchez (2012) it was proved that given an mm-colored digraph DD, if C(D) is cyclically 2-partite then DD has a kernel by monochromatic paths (that is a 1-colored kernel). In this paper we extend this work and prove the following: Let  DDbe a strongly connected  mm-colored digraph  DDsuch that, for some  k≥1k≥1,  C(D)is a cyclically  (k+1)(k+1)-partite digraph, with partition  {Ci}i=0k. (i) If for some part  Cj, no vertex of  Cjhas a loop, then  DDhas a  kk-colored kernel. (ii) For each  ii, with  0≤i≤k0≤i≤k, let  DiDibe the subgraph of  DDinduced by the set of arcs with color in  Ci, and for each vertex  xxof  DDlet  NC+(x)and  NC−(x)be the set of colors appearing in the ex-arcs and in-arcs of  xx, respectively. If for some subdigraph  DjDj, for every vertex  xxof  DjDjwe have that  NC+(x)⊈NC−(x), then  DDhas a  kk-colored kernel.As a direct consequence we obtain a proof of Richardson’s Theorem in the case DD is strongly connected, and a proof of a classical result by M. Kwaśnik (see Kwaśnik (1983) ) on the existence of kk-kernels (a kk-kernel of a digraph D=(V,A)D=(V,A) is a set S⊆VS⊆V such that for any v∈V∖Sv∈V∖S, dD(v,S)≤k−1dD(v,S)≤k−1 and for every pair {u,v}⊆S{u,v}⊆S, dD(u,v)≥kdD(u,v)≥k) that asserts that if DD is a strongly connected digraph such that every directed cycle has length congruent with 0 modulo kk, then DD has a kk-kernel.