کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648886 | 1342434 | 2010 | 8 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 310, Issue 20, 28 October 2010, Pages 2697–2704