Exact value of mader_χ̄(K̄ₙ)

Problem 12 · arXiv:1610.00876

arXiv Problem high confidence— first stated 2016-10-04

Authors: Pierre Aboulker, Nathann Cohen, Fréderic Havet, William Lochet, Phablo F. S. Moura, Stéphan Thomassé

Status open high confidence

Problem 12 asks for the exact value of $\mathrm{mader}_{\vec{\chi}}(\vec{K}_n)$; the source paper only establishes the doubly-exponential upper bound $4^{n^2-2n+1}(n-1)+1$. The most relevant follow-up, Gishboliner–Steiner–Szabó (2020, arXiv:2008.09888), proves $\mathrm{mader}_{\vec{\chi}}(F)=v(F)$ for octus digraphs and orientations of cactus graphs, but the complete digraph $\vec{K}_n$ falls outside these classes and the exact value remains unknown. No paper resolving Problem 12 was found in the indexed literature.

Cited literature (2)

partial Dichromatic number and forced subdivisions (2020)

Lior Gishboliner, Raphael Steiner, Tibor Szabó · Journal of Combinatorial Theory, Series B · arXiv:2008.09888 · doi:10.1016/j.jctb.2021.06.003

Proves $\mathrm{mader}_{\vec{\chi}}(F)=v(F)$ for every octus digraph $F$ and for every orientation of a cactus graph; $\vec{K}_n$ is not in these classes, so the exact value of $\mathrm{mader}_{\vec{\chi}}(\vec{K}_n)$ is not settled.
partial Oriented cycles in digraphs of large outdegree (2020)

Lior Gishboliner, Raphael Steiner, Tibor Szabó · arXiv preprint · arXiv:2008.13224

Proves that every digraph with minimum out-degree at least $K(\ell)$ contains a subdivision of every orientation of a cycle of length $\ell$; addresses $\mathrm{mader}_{\delta^+}$ for oriented cycles rather than $\mathrm{mader}_{\vec{\chi}}(\vec{K}_n)$.

Reviewer notes. The search also surfaced arXiv:2101.04590 (Mészáros–Steiner, 2021, 'Complete minors in digraphs with given dichromatic number'), which improves bounds on forced complete *minors* under dichromatic number; minors are weaker than subdivisions and this paper does not resolve Problem 12. No paper giving the exact value of mader_chi(K_n) was found.

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

Problem. What is $\mathrm{mader}_{\vec{\chi}}(\vec{K}_n)$?

Context

The paper proves in Section 3 that every digraph is $\vec{\chi}$-maderian. Since every digraph of order $n$ is a subdigraph of $\vec{K}_n$, bounding $\mathrm{mader}_{\vec{\chi}}(\vec{K}_n)$ controls all cases. The paper establishes $\mathrm{mader}_{\vec{\chi}}(\vec{K}_n) \leq 4^{n^2-2n+1}(n-1)+1$ (Corollary 36), but the exact value is unknown.

Notes. PDF source — dichromatic number denoted $\vec{\chi}$; upper bound exponent reconstructed from context as $n^2-2n+1 = n(n-1)-n+1$ for $\vec{K}_n$ with $n(n-1)$ arcs and 1 component.

Source paper

Subdivisions in digraphs of large out-degree or large dichromatic number
Pierre Aboulker, Nathann Cohen, Fréderic Havet, William Lochet, Phablo F. S. Moura, Stéphan Thomassé · 2016-10-04
https://arxiv.org/abs/1610.00876 PDF source