부산대학교 도서관

A problem attributed to Erdős asks whether, given an integer $k\ge1$, there exists an integer $f(k)$ so that every $k$-arc-coloredtournament contains a set $S$ of at most $f(k)$ vertices such that forevery vertex $y$ not in $S$, there exists a monochromatic directed pathfrom $y$ to some vertex in $S$. That $f(1)=1$ follows by a text booktheorem 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, Sauerand Woodrow [op. cit.] conjectured that every 3-arc-colored tournament thatcontains no rainbow 3-cycles contains a monochromatic sink. (Anarc-colored directed 3-cycle is called a rainbow if no two arcs havethe same color, and a vertex $x$ in an arc-colored tournament is calleda monochromatic sink if, for every vertex $y$, there is a monochromaticdirected path from $y$ to $x$.) This conjecture too is open. There havebeen several partial results on variations of the above two problemsand some with additional assumptions. In the paper under review, theauthors show that any arc-colored tournament (with an arbitrary numberof colors) contains a monochromatic sink if it satisfies the followingtwo conditions: (1) it contains no rainbow 3-cycles, and (2) it contains asubset $F$ of at most two arcs whose direction reversal yields atransitive tournament. Examples are also given to show that the resultdoes not hold if $|F| = 3$.