Reachability problems in edge-colored digraphs (Q2643322)

Let \(G\) be a multidigraph whose arcs are colored with the vertices of a digraph \(D\). A walk \(W\) in \(G\) is a \(D\)-walk if the consecutive colors encountered on \(W\) form a walk in \(D\). A set \(S\) of vertices of \(G\) is a \(D\)-sink if every vertex not in \(S\) can reach some vertex in \(S\) via a \(D\)-walk. Let \(B_1,B_2\), and \(B_3\) denote the set of digraphs \(D\) such that every finite \(D\)-arc-colored multidigraph \(G\) has a \(D\)-sink \(S\) such that (1) \(|S|=1\), or (2) no two vertices of \(S\) are joined by an arc, or (3) no two vertices of \(S\) have a \(D\)-walk between them, respectively. The authors characterize the set \(B_2\) and show that \(B_1\subset B_2\subset B_3\), where the inclusions are strict, among other things.