Sands, Bill


Monochromatic reachability in arc-colored digraphs ★★★

Author(s): Sands; Sauer; Woodrow

\begin{conjecture} For every $k$, there exists an integer $f(k)$ such that if $D$ is a digraph whose arcs are colored with $k$ colors, then $D$ has a $S$ set which is the union of $f(k)$ stables sets so that every vertex has a monochromatic path to some vertex in $S$. \end{conjecture}

Keywords:

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

Syndicate content