Reachability Problems in Edge-colored Tournaments

Abstract:

In 1982 Sands, Sauer and Woodrow proved a theorem with the following corollary: If the arcs of a tournament are 2-colored, then there is a vertex v (called a sink) in the tournament such that any other vertex in the tournament has a monochromatic directed path into v. Since then this corollary has been generalized and similar results have appeared. Here we investigate a natural generalization, where the colors on the arcs of the tournament are the vertices of a directed graph, $D$, and a directed walk in the tournament is D-admissible iff the colors on the arcs of the walk in the tournament also form a walk in D. For example, if D has just two vertices and each vertex has a loop to itself, then the walks/paths that are D-admissible are exactly the monochromatic walks/paths. We call D 1-sinkable if any arc coloring of any tournament has a sink that can be reached from any other vertex on a D-admissible walk; so the 1982 result of Sands et. al. says that the digraph of two loops is 1-sinkable. We will give examples of other 1-sinkable digraphs, and a striking counter example that refutes an obvious conjecture characterizing the property of 1-sinkability.