D₅-free condition necessity in strong EH-property

Informal question: can the D5-freeness hypothesis in Theorem 1.6 be dropped? · arXiv:2202.13977

arXiv Informal medium confidence— first stated 2023-08-08

Authors: Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Status open high confidence

Theorem 1.6 of arXiv:2202.13977 shows that if a tournament H admits a numbering whose backedge graph has at most three edges and H is D5-free, then H has the strong EH-property; the D5-freeness condition excludes exactly the case where the three backedges form the backedge graph of D5. The authors leave open whether this condition can be omitted. A web search covering literature through May 2026 found no follow-up paper resolving this question.

Reviewer notes. No follow-up resolving the D5-freeness question was found in the indexed literature. The related paper arXiv:2402.10782 (NP-completeness of finding forest-orderings of tournaments) cites the broader conjecture about forest-ordered tournaments and the strong EH-property but does not address the D5-free condition specifically. The conjecture is recent (preprint 2022, published 2024) and the absence of a follow-up is consistent with it remaining open.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. Perhaps the second sentence in 1.6 (the condition that $H$ is $D_5$-free) can be omitted, but that remains open.

Context

Theorem 1.6 states that if a tournament $H$ admits a numbering $(v_1,\ldots,v_n)$ whose backedge graph $B$ has at most three edges, and $H$ is $D_5$-free, then $H$ has the strong EH-property. The $D_5$-freeness condition excludes exactly the case where the three backedges form the unique three-edge backedge graph of $D_5$; the authors leave open whether this exclusion is truly necessary.

Source paper

Pure pairs. X. Tournaments and the strong Erdos-Hajnal property
Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl · 2023-08-08
https://arxiv.org/abs/2202.13977 PDF source