Reachability problems in edge-colored digraphs

AbstractLet D be a digraph and let G be a multidigraph whose arcs are colored with the vertices of D. A walk, W, in G is a D-walk if the consecutive colors encountered on W also form a walk in D. A set S⊆V(G) is a D-sink if any x∈V(G)-S reaches some y∈S on a D-walk. We say S is D-independent (resp. independent) if no two vertices of S have a D-walk (resp. have an arc) between them. Let D∈B2 (resp. D∈B3) if any finite D arc-colored digraph G always has an independent (resp. D-independent) D-sink, and let D∈B1 if any finite D arc-colored tournament always has a 1-point D-sink. Sands et al. [On monochromatic paths in edge-colored digraphs, J. Combin. Theory Ser. B 33 (1982) 271–275.] showed that if D has vertex set {red,blue} and arcs (red,red), (blue,blue) then D∈B3, a D-walk then being just a monochromatic walk.Here we give a classification of B2, and make inroads in the classification of B3 and B1, as well we prove the strict containment B3⊊B2⊊B1. Finally, we generalize these problems by considering D to be an automaton and replacing D by the language accepted by D