Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648886 | Discrete Mathematics | 2010 | 8 Pages |
Let TT be the set of all arc-colored tournaments, with any number of colors, that contain no rainbow 3-cycles, i.e., no 3-cycles whose three arcs are colored with three distinct colors. We prove that if T∈TT∈T and if each strong component of TT is a single vertex or isomorphic to an upset tournament, then TT contains a monochromatic sink. We also prove that if T∈TT∈T and TT contains a vertex xx such that T−xT−x is transitive, then TT contains a monochromatic sink. The latter result is best possible in the sense that, for each n≥5n≥5, there exists an nn-tournament TT such that (T−x)−y(T−x)−y is transitive for some two distinct vertices xx and yy in TT, and TT can be arc-colored with five colors such that T∈TT∈T, but TT contains no monochromatic sink.