학술논문

Monochromatic sinks in arc-colored tournaments with small feedback arc sets.
Document Type
Journal
Author
Melcher, M. (1-CASSM) AMS Author Profile; Reid, K. B. (1-CASSM) AMS Author Profile
Source
Bulletin of the Institute of Combinatorics and its Applications (Bull. Inst. Combin. Appl.) (20110101), 62, 79-89. ISSN: 1183-1278 (print).eISSN: 2689-0674.
Subject
05 Combinatorics -- 05C Graph theory
  05C15 Coloring of graphs and hypergraphs
Language
English
ISSN
26890674
Abstract
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$.

Online Access