The forest characterization conjecture for the strong Erdős–Hajnal property

Let HH be a tournament, and let an ordering of its vertices determine its backward arc digraph, whose edges are the arcs directed backward relative to that ordering. A tournament has the strong Erdős–Hajnal property if there exists lpha>0lpha>0 such that every HH-free tournament TT with more than one vertex has disjoint sets A,BV(T)A,B\subseteq V(T), every vertex of AA adjacent to every vertex of BB, and min(A,B)αT\min(|A|,|B|)\geq \alpha|T|.

Forest characterization conjecture. If a tournament HH has an ordering of its vertices for which the backward arc digraph is a forest, then HH has the strong Erdős–Hajnal property.

Chudnovsky et al. proved the converse implication: the strong Erdős–Hajnal property forces an ordering whose backward arc digraph is a forest. The stated implication remains open.

Sources & referencesView supporting material

Primary source

Soukaina Zayat, “Forests and the Strong Erdos-Hajnal Property”, arXiv:2207.09146 (2022).

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.