Optimal balanced bi-tree size constant

Problem 2 · arXiv:2304.03567

arXiv Problem high confidence— first stated 2024-01-11

Authors: Stéphane Bessy, Stéphan Thomassé, Laurent Viennot

Status open high confidence

Problem 2 of arXiv:2304.03567 asks for the maximum constant $c_b$ such that every strongly connected directed graph on $n$ vertices has a balanced bi-tree of size at least $c_b \cdot n$. The source paper establishes $c_b \geq 1/3$ (Theorem 4), with both the out-tree and in-tree of size at least $n/6$ each. No subsequent work improving this bound or determining the exact value of $c_b$ was found in a thorough web search.

Reviewer notes. No follow-up work found after 5 web calls. The conjecture was published at STACS 2024 and remains open. The internal references supplied (arXiv:2206.12335, twice) are false matches from the fuzzy-matching pipeline — they concern 1-independent percolation on Z^n and have no connection to this problem.

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

Problem. What is the maximum $c_{b}$ for which every strongly connected directed graph on $n$ vertices has a balanced bi-tree of size at least $c_{b}.n$?

Context

The paper proves $c_{b}\geq 1/3$ (Theorem 4), where both the out-tree $|T^{+}|$ and in-tree $|T^{-}|$ of the bi-tree each have size at least $n/6$. The exact optimal constant $c_{b}$ is unknown.

Source paper

Temporalizing digraphs via linear-size balanced bi-trees
Stéphane Bessy, Stéphan Thomassé, Laurent Viennot · 2024-01-11
https://arxiv.org/abs/2304.03567