부산대학교 도서관

A problem attributed to Erdős asks whether, given an integer $k\ge 1$, there exists an integer $f(k)$ so that every $k$-arc-colored tournament contains a set $S$ of at most $f(k)$ vertices such that for every vertex $y$ not in $S$, there exists a monochromatic directed path from $y$ to some vertex in $S$. That $f(1)=1$ follows by a text book theorem that every tournament contains a directed Hamilton path. That $f(2)=1$ was proved by B. Sands, N.~W. Sauer and R.~E. Woodrow [J. Combin. Theory Ser. B {\bf 33} (1982), no.~3, 271--275; MR0693367 (84e:05052)]. The problem is open for $k\ge 3$. Sands, Sauer and Woodrow [op. cit.] conjectured that every 3-arc-colored tournament that contains no rainbow 3-cycles contains a monochromatic sink. (An arc-colored directed 3-cycle is called a rainbow if no two arcs have the same color, and a vertex $x$ in an arc-colored tournament is called a monochromatic sink if, for every vertex $y$, there is a monochromatic directed path from $y$ to $x$.) This conjecture too is open. There have been several partial results on variations of the above two problems and some with additional assumptions. In the paper under review, the authors show that any arc-colored tournament (with an arbitrary number of colors) contains a monochromatic sink if it satisfies the following two conditions: (1) it contains no rainbow 3-cycles, and (2) it contains a subset $F$ of at most two arcs whose direction reversal yields a transitive tournament. Examples are also given to show that the result does not hold if $|F| = 3$.