Strong EH-property via backedge forest tournaments

Status open high confidence

Conjecture 1.5 of arXiv:2202.13977 asserts that the strong EH-property for tournaments is characterised exactly by the existence of a numbering whose backedge graph is a forest. The necessary direction (strong EH-property implies forest numbering) was established as Theorem 1.4 in the source paper, but the converse remains open. A 2024 paper (arXiv:2402.10782) proved that deciding whether a tournament admits such a forest-ordering is NP-complete, which is computationally related to the conjecture but does not resolve it.

Cited literature (1)

• partial Finding forest-orderings of tournaments is NP-complete (2024)
  (not extracted from abstract page) · arXiv preprint · arXiv:2402.10782

  Proves that the problem of deciding whether a tournament admits a forest-ordering (equivalently, a feedback arc set inducing a forest) is NP-complete; explicitly motivated by the connection to the strong Erdos-Hajnal property but does not resolve Conjecture 1.5.

Reviewer notes. The conjecture is recent (posted 2022, published 2023). The only post-statement follow-up found is arXiv:2402.10782 (2024), which addresses the computational complexity of verifying the forest-ordering condition (NP-complete) rather than the logical equivalence itself. No counterexample or proof of the converse direction was found. Conjecture 1.5 remains fully open.

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