2020/06/05 by Hernández-Lorenzana, Felipe, Sánchez-López, Rocío
#05C20 #05C38 #05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2006.03691
Let H be a digraph possibly with loops and D a digraph without loops with a coloring of its arcs c:A(D) → V(H) (D is said to be an H-colored digraph). A directed path W in D is said to be an H-path if and only if the consecutive colors encountered on W form a directed walk in H. A subset N of vertices of D is said to be an H-kernel if (1) for every pair of different vertices in N there is no H-path between them and (2) for every vertex u in V(D)∖N there exists an H-path in D from u to N. Under this definition an H-kernel is a kernel whenever A(H)=∅. The color-class digraph \mathscrCC(D) of D is the digraph whose vertices are the colors represented in the arcs of D and (i,j) ∈ A(\mathscrCC(D)) if and only if there exist two arcs, namely (u,v) and (v,w) in D, such that (u,v) has color i and (v,w) has color j. Since not every H-colored digraph has an H-kernel and V(\mathscrCC(D))= V(H), the natural question is: what structural properties of \mathscrCC(D), with respect to the H-coloring, imply that D has an H-kernel? In this paper we investigate the problem of the existence of an H-kernel by means of a partition ξ of V(H) and a partition \ξ1, ξ2\ of ξ. We establish conditions on the directed cycles and the directed paths of the digraph D, with respect to the partition \ξ1, ξ2\. In particular we pay attention to some subestructures produced by the partitions ξ and \ξ1, ξ2\, namely (ξ1, ξ, ξ2)-H-subdivisions of \overrightarrowC3 and (ξ1, ξ, ξ2)-H-subdivisions of \overrightarrowP3. We give some examples which show that each hypothesis in the main result is tight.