tournament


PTAS for feedback arc set in tournaments ★★

Author(s): Ailon; Alon

\begin{question} Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments? \end{question}

Keywords: feedback arc set; PTAS; tournament

Monochromatic reachability or rainbow triangles ★★★

Author(s): Sands; Sauer; Woodrow

In an edge-colored digraph, we say that a subgraph is \emph{rainbow} if all its edges have distinct colors, and \emph{monochromatic} if all its edges have the same color.

\begin{problem} Let $G$ be a tournament with edges colored from a set of three colors. Is it true that $G$ must have either a rainbow directed cycle of length three or a vertex $v$ so that every other vertex can be reached from $v$ by a monochromatic (directed) path? \end{problem}

Keywords: digraph; edge-coloring; tournament

Monochromatic reachability in edge-colored tournaments ★★★

Author(s): Erdos

\begin{problem} For every $n$, is there a (least) positive integer $f(n)$ so that whenever a tournament has its edges colored with $n$ colors, there exists a set $S$ of at most $f(n)$ vertices so that every vertex has a monochromatic path to some point in $S$? \end{problem}

Keywords: digraph; edge-coloring; tournament

Syndicate content