Strong Erdős–Hajnal conjecture for simple digraphs
Let be a tournament, let be a simple digraph on vertices with no subdigraph isomorphic to , and let denote its largest acyclic set. Strong Erdős–Hajnal conjecture. For every tournament there exists such that
This strengthens the tournament Erdős–Hajnal conjecture from oriented tournaments to arbitrary -free simple digraphs. The paper gives an upper bound when has vertices, while the general conjecture remains open.
References
Primary source
Ararat Harutyunyan, Colin McDiarmid and Gil Puig i Surroca, “Acyclic sets and colorings in digraphs under restrictions on degrees and cycle lengths”, arXiv:2603.02947 (2026).
Progress summary
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.