The forest characterization conjecture for the strong Erdős–Hajnal property
The forest characterization conjecture for the strong Erdős–Hajnal property
Let 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 such that every -free tournament with more than one vertex has disjoint sets , every vertex of adjacent to every vertex of , and .
Forest characterization conjecture. If a tournament has an ordering of its vertices for which the backward arc digraph is a forest, then 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.