Monochromatic sinks in nearly transitive arc-colored tournaments

Abstract

Let T 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 ∈ T and if each strong component of T is a single vertex or isomorphic to an upset tournament, then T contains a monochromatic sink. We also prove that if T ∈ T and T contains a vertex x such that T − x is transitive, then T contains a monochromatic sink. The latter result is best possible in the sense that, for each n ≥ 5, there exists an n-tournament T such that (T−x)−y is transitive for some two distinct vertices x and y in T , and T canbe arc-coloredwith five colors such that T ∈ T , but T contains nomonochromatic sink. © 2010 Elsevier B.V. All rights reserved.

Topics

0 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)