The Erdős–Sands–Sauer–Woodrow path-domination conjecture

Let a tournament have its edges colored with kk colors. A set SS of vertices has the path-domination property if every vertex outside SS can be reached from some vertex of SS by a monochromatic directed path.

Erdős–Sands–Sauer–Woodrow conjecture. For each positive integer kk there is a least integer f(k)f(k) such that every kk-colored tournament contains a set SS of f(k)f(k) vertices with the path-domination property. In particular, does f(3)f(3) exist, and is f(3)=3f(3)=3?

The paper identifies this as a well-known conjecture and cites subsequent work for further developments. The provided text does not state that it has been resolved.

Sources & referencesView supporting material

Primary source

Dömötör Pálvölgyi and András Gyárfás, “Domination in transitive colorings of tournaments”, arXiv:1302.4677 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.