Importance: High ✭✭✭
Recomm. for undergrads: no
Posted by: mdevos
on: July 15th, 2008

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}

This problem was raised in a paper by Sands, Sauer, and Woodrow [SSW] where they prove that every tournament with 2-colored edges has a vertex $v$ so that every other vertex can be reached from $v$ by a monochromatic path.

Galeana-Sanchez and Rojas-Monroy found a tournament on 6 vertices with 4-colored edges which has no rainbow triangle and does not have a vertex $v$ which has monochromatic paths to all remaining vertices. However, the following generalization of the above conjecture looks plausible.

\begin{problem} Does every edge-colored tournament have either a rainbow directed cycle or a vertex $v$ so that every other vertex can be reached from $v$ by a monochromatic path? \end{problem}

Bibliography

*[SSW] B. Sands, N. Sauer, R. Woodrow, \href[On monochromatic paths in edge-coloured digraphs]{http://www.sciencedirect.com/science/article/pii/0095895682900478}. J. Combin. Theory Ser. B 33 (1982), no. 3, 271--275. \MRhref{MR0693367}.


* indicates original appearance(s) of problem.

Reply

Comments are limited to a maximum of 1000 characters.