Strong Erdős–Hajnal conjecture for simple digraphs
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
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).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.