کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648886 1342434 2010 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Monochromatic sinks in nearly transitive arc-colored tournaments
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Monochromatic sinks in nearly transitive arc-colored tournaments
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issue 20, 28 October 2010, Pages 2697–2704
نویسندگان
, ,