HH-kernels and HH-obstructions in HH-colored digraphs

Let DD be a digraph. V(D)V(D) and A(D)A(D) will denote the vertex and arc sets of DD respectively. A kernel KK of a digraph DD is an independent set of vertices of DD such that for every vertex ww in V(D)V(D)-KK there exists an arc from ww to a vertex in KK. Let HH be a digraph possibly with loops and DD a digraph without loops whose arcs are colored with the vertices of HH (DD is said to be an HH-colored digraph). A directed path WW in DD is said to be an HH-path if and only if the consecutive colors encountered on WW form a directed walk in HH. A generalization of the concept of kernel is the concept of HH-kernel, where an HH-kernel NN of an HH-colored digraph DD is a set of vertices of DD such that for every pair of different vertices in NN there is no HH-path between them, and for every vertex uu in V(D)V(D)-NN there exists an HH-path in DD from uu to NN. A classical result in kernel theory establishes that if DD is a digraph without cycles of odd length, then DD has a kernel; this result is known as Richardson’s theorem and in this paper we will show an extension of this theorem which is given by the main result.Let DD be an HH-colored digraph. For an arc (z1z1, z2z2) of DD we will denote its color by cc(z1z1, z2z2). We introduce the concept of obstruction   in an HH-colored digraph as follows. Let W=(v0,v1,…,vn−1,v0)W=(v0,v1,…,vn−1,v0) be a closed directed walk in DD. We will say that there is an obstruction on vivi if (cc(vi−1vi−1, vivi), cc(vivi, vi+1vi+1)) is not an arc of A(H)A(H) (indices modulo nn). The main result establishes that if DD is an HH-colored digraph such that the number of obstructions in every closed directed trail of DD is even, then DD has an HH-kernel. Previous interesting results are generalized, as for example Sands, Sauer and Woodrow’s theorem.