H-Kernels in Unions of H-Colored Quasi-Transitive Digraphs

Abstract

Let H be a digraph (possibly with loops) and D a digraph without loops whose arcs are colored with the vertices of H (D is said to be an H-colored digraph). For an arc (x, y) of D, its color is denoted by c(x, y). A directed path W = (v0, . . ., vn) in an H-colored digraph D will be called H-path if and only if (c(v0, v1), . . ., c(vn−1, vn)) is a directed walk in H. In W, we will say that there is an obstruction on viif (c(vi−1, vi), c(vi, vi+1)) /∉ A(H) (if v0 = vnwe will take indices modulo n). A subset N of V (D) is said to be an H-kernel in D if for every pair of di erent vertices in N there is no H-path between them, and for every vertex u in V (D) \ N there exists an H-path in D from u to N. Let D be an arc-colored digraph. The color-class digraph of D, 𝒞C(D), is the digraph such that V (𝒞C(D)) = {c(a) : a ∈ A(D)} and (i, j) ∈ A(𝒞C(D)) if and only if there exist two arcs, namely (u, v) and (v, w) in D, such that c(u, v) = i and c(v, w) = j. The main result establishes that if D = D1 ∪ D2 is an H-colored digraph which is a union of asymmetric quasi-transitive digraphs and {V1, . . ., Vk} is a partition of V (𝒞C(D)) with a property P* such that

Keywords

• quasi-transitive digraph
• kernel by monochromatic paths
• alternating kernel
• h-kernel
• obstruction
• 05c20
• 05c38
• 05c69