Height function characterizing non-avoidable digraphs

Question 6.2 · arXiv:2510.11311

arXiv Question high confidence— first stated 2025-10-13

Authors: Micha Christoph, Barnabás Janzer, Kalina Petrova, Raphael Steiner

Status open high confidence

Question 6.2 asks whether every digraph admitting a height function is non-avoidable, motivated by the observation that all digraphs proved non-avoidable in the paper (one-directed complete bipartite graphs and oriented trees) do allow a height function. The paper was posted in October 2025 and no follow-up resolving this question was found in the literature as of May 2026. The question remains open alongside related open problems (Conjecture 6.1 on odd-cycle orientations, Questions 6.3–6.4 on C4 orientations), all part of the broader program of characterizing avoidable digraphs.

Reviewer notes. No follow-up paper addressing Question 6.2 found after 3 web searches and fetching both the arXiv abstract page and the HTML full text. The question is recent (October 2025) and is explicitly posed as open by the authors. The HTML version of the paper confirms the exact statement and motivation of Question 6.2.

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

Question. Are all digraphs which allow a height function not avoidable?

Context

All digraphs for which the authors proved non-avoidability (including one-directed complete bipartite graphs and oriented trees) allow a height function. This observation motivates asking whether the existence of a height function fully characterizes non-avoidable digraphs.

Source paper

Extending Thomassen's conjecture to directed graphs
Micha Christoph, Barnabás Janzer, Kalina Petrova, Raphael Steiner · 2025-10-13
https://arxiv.org/abs/2510.11311