2-extremal digraph characterization via χ and λ

Conjecture 9.2 · arXiv:2304.04690

arXiv Conjecture high confidence— first stated 2023-09-13

Authors: Pierre Aboulker, Guillaume Aubian, Pierre Charbit

Status open high confidence

Conjecture 9.2 asserts that a digraph is 2-extremal if and only if it belongs to $\mathcal{H}_2$, the class generated from symmetric odd cycles by directed Hajós joins and 2-Hajós tree joins. This complements the paper's characterization for $k=1$ and $k\geq 3$. No follow-up resolving the $k=2$ case was found in the May 2026 review.

Reviewer notes. The exact statement was verified as Conjecture 9.2 in the complete cached PDF; the earlier extraction had stopped before Section 9.

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

Conjecture. A digraph is 2-extremal if and only if it is in $\mathcal{H}_2$.

Context

The paper defines $\mathcal{H}_2$ as the smallest class containing symmetric odd cycles and closed under directed Hajós joins and 2-Hajós tree joins. Its main theorem characterizes $k$-extremal digraphs for $k=1$ and $k\geq 3$; Conjecture 9.2 proposes the missing characterization for $k=2$.

Notes. Statement restored from Conjecture 9.2 in the complete cached PDF.

Source paper

Digraph Colouring and Arc-Connectivity
Pierre Aboulker, Guillaume Aubian, Pierre Charbit · 2023-09-13
https://arxiv.org/abs/2304.04690 PDF source