κ-maderianness of strongly connected digraphs

Problem 16 · 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 partial medium confidence

Problem 16 asks two questions: whether all digraphs are $\kappa$-maderian (large strong connectivity forces subdivisions) and whether all digraphs are $\kappa'$-maderian (large strong arc-connectivity forces subdivisions). The $\kappa'$-maderian question was answered negatively by Gishboliner, Steiner, and Szabó (arXiv:2008.13224, Propositions 10--11), who showed that neither $\overleftrightarrow{K_4}$ nor $\overleftrightarrow{S_4}$ is $\kappa'$-maderian. The $\kappa$-maderian question remains open; Thomassen's Conjecture 17 from the source paper would imply a positive answer for that part.

Cited literature (1)

counterexample Oriented cycles in digraphs of large outdegree (2021)

Lior Gishboliner, Raphael Steiner, Tibor Szabó · Combinatorica · arXiv:2008.13224 · doi:10.1007/s00493-021-4750-z

Proves (Propositions 10 and 11) that neither $\overleftrightarrow{K_4}$ nor $\overleftrightarrow{S_4}$ is $\kappa'$-maderian, answering the $\kappa'$-maderian half of Problem 16 negatively; the $\kappa$-maderian question is noted as remaining open.

Reviewer notes. The three internal references for arXiv:2008.13224 are contradictory because the fuzzy matcher extracted text associated with different problems in the source paper. The fuzz=80 entry is the most specific to Problem 16. The κ-maderian question (strong connectivity version) remains open as of the latest literature found. No additional follow-up papers beyond arXiv:2008.13224 were found in the web search.

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

Problem. Are all digraphs $\kappa$-maderian? $\kappa'$-maderian?

Context

Since $k$-connected graphs have minimum degree at least $k$, Mader's undirected theorem implies graphs with connectivity at least $g(k)$ contain a $K_k$ subdivision. The analogous question for strong connectivity $\kappa(D)$ and strong arc-connectivity $\kappa'(D)$ of digraphs is open. Thomassen's Conjecture 17 would imply a positive answer for $\kappa$-maderianness.

Notes. PDF source.

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