login/create account
Monochromatic reachability or rainbow triangles
In an edge-colored digraph, we say that a subgraph is rainbow if all its edges have distinct colors, and monochromatic if all its edges have the same color.
Problem Let 
be a tournament with edges colored from a set of three colors. Is it true that must have either a rainbow directed cycle of length three or a vertex 
so that every other vertex can be reached from by a monochromatic (directed) path?
be a tournament with edges colored from a set of three colors. Is it true that must have either a rainbow directed cycle of length three or a vertex so that every other vertex can be reached from by a monochromatic (directed) path? 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 so that every other vertex can be reached from 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 which has monochromatic paths to all remaining vertices. However, the following generalization of the above conjecture looks plausible.
Problem Does every edge-colored tournament have either a rainbow directed cycle or a vertex so that every other vertex can be reached from by a monochromatic path?
so that every other vertex can be reached from by a monochromatic path? Bibliography
*[SSW] B. Sands, N. Sauer, R. Woodrow, On monochromatic paths in edge-coloured digraphs. J. Combin. Theory Ser. B 33 (1982), no. 3, 271--275. MathSciNet.
* indicates original appearance(s) of problem.
Drupal
CSI of Charles University