Graph-theory open problems

Monochromatic reachability or rainbow triangles

High ★★★ Graph Theory » Directed Graphs » Tournaments
Authors: Sands, Bill, Sauer, Norbert W., Woodrow, Robert E.— posted by mdevos on 2008-07-15

Status partial medium confidence

The conjecture that every 3-edge-colored tournament has either a rainbow directed triangle or a vertex from which all others are reachable by a monochromatic path remains open. Georgakopoulos and Sprüssel (2009) established a partial case: the conclusion holds for every 3-edge-colored tournament in which no vertex is incident with all three colors. The generalized conjecture (arbitrary number of colors) is also open, with the 4-color case shown to be false by a counterexample that predates the OPG posting.

Cited literature (1)

  • partial On 3-coloured tournaments (2009)
    Agelos Georgakopoulos, Philipp Sprüssel · arXiv preprint · arXiv:0904.1967

    Proves that every 3-edge-colored tournament in which no vertex is incident with all three colors contains either a rainbow directed triangle or a vertex with monochromatic paths to all other vertices, establishing the conjecture under this additional assumption.

Reviewer notes. The Douglas West problem page (dwest.web.illinois.edu/regs/msourcyc.html, citations through 2010) confirms the 3-color conjecture is still open. The Georgakopoulos-Sprüssel arXiv preprint notes their main result 'had appeared before' in another work, meaning the partial result under extra conditions may predate the OPG posting; nonetheless the paper itself is from 2009. The 'Monochromatic Sinks in k-Arc Colored Tournaments' (Springer 2015) and related journal papers could not be fully accessed due to paywalls and may contain further partial progress. No paper found that resolves the main conjecture.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 02) (web search enabled).

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?
Keywords: digraph · edge-coloring · tournament

Discussion

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. 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?

Bibliography