Originated by: B. Sands, N. Sauer, and R. Woodrow (presented by Elyse Yeager - REGS 2011; see earlier appearance on the Open Problem Garden)
Definitions: A vertex v in an edge-colored digraph is a monosource if for every x∈V(G), there is a monochromatic v,x-path. A rainbow cycle is a consistently directed cycle whose edges have distinct colors.
Background: In Ramsey theory, a fixed number of colors is used to color elements of a large object, and we seek a monochromatic occurrence of a particular substructure. Pattern Ramsey theory is more general; the number of colors need not be fixed, and we seek one of some set of patterns, where a pattern is a structure whose elements are grouped into sets such that those in a set must have the same color and those in different sets must have different colors. Monochromatic and rainbow structures are patterns; see [JJL]. There are several results related to undirected pattern Ramsey problems involving rainbow triangles. For example, every edge-colored complete graph contains a monochromatic spanning tree or a rainbow triangle [GS]; see also [GSSS].
Conjecture 1: [SSW] In any 3-edge-coloring of a tournament, there is a monosource or a rainbow 3-cycle.
Problem 2: Is it true that every r-edge-colored tournament has a monosource or a rainbow cycle?
Comments: [SSW] proved that a 2-edge-colored tournament has a monosource. The conclusion for 3-edge-colorings holds if the requirement that the triple be directed as a cycle is dropped. For n≥6, Galeana-Sánchez and Rojas-Monroy [GR] constructed a 4-edge-colored n-vertex tournament having no monosource and no rainbow 3-cycle.
References:
[SSW] B. Sands, N. Sauer, R. Woodrow; On monochromatic paths in
edge-coloured digraphs, J.
Combin. Theory Ser. B 33 (1982), 271–275
[GR] H. Galeana-Sánchez, R. Rojas-Monroy; A
counterexample to a conjecture on edge-coloured tournaments.
Discrete Mathematics 282(1-3) (2004) 275-276.
[GS] A. Gyárfás, G. Simonyi, Edge colorings of complete graphs
without tricolored triangles, Journal of Graph Theory 46 (2004), 211-216.
[GSSS] A. Gyárfás, G.N. Sárközy, A. Sebő,
S. Selkow; Ramsey-type results for Gallai colorings.
J. Graph Theory 64 (2010), 233-243.
[JJL] R.E. Jamison, T. Jiang, A.C. Ling;
Constrained Ramsey numbers of graphs.
J. Graph Theory 42 (2003), 1-16.