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

At least 12 years old · documented by

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.

References

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.