Decomposing k-arc-strong tournament into k spanning strong digraphs

Medium ★★ Graph Theory » Directed Graphs » Tournaments

Authors: Bang-Jensen, Joergen, Yeo, Anders— posted by fhavet on 2013-03-15

Status partial medium confidence

The conjecture that every $k$-arc-strong tournament decomposes into $k$ spanning strong digraphs remains open. The best known partial result from Bang-Jensen and Yeo (2004) covers $k$-arc-strong tournaments with minimum in- and out-degree at least $37k$. Post-2013 work has extended arc-disjoint strong spanning subdigraph results to broader classes (semicomplete compositions) but has not resolved the original conjecture for tournaments.

Cited literature (1)

partial Arc-disjoint Strong Spanning Subdigraphs of Semicomplete Compositions (2019)

Joergen Bang-Jensen, Gregory Gutin, Anders Yeo · arXiv preprint · arXiv:1903.12225

Characterizes digraph compositions (with a semicomplete base digraph) that admit a strong arc decomposition, extending the framework of Bang-Jensen–Yeo to a broader class than tournaments.

Reviewer notes. The Wiley Online Library pages for 'Strong arc decompositions of split digraphs' (JGT 2025) and 'Making a tournament k-strong' (JGT 2023) and 'Arc-disjoint strong spanning subdigraphs of semicomplete compositions' (JGT 2020) returned HTTP 403 and could not be verified. The 2024 arXiv paper 2408.02260 on split digraphs is related but does not address the tournament conjecture directly. No post-2013 paper resolving the original conjecture was found in 4 search rounds. Kelly's conjecture (implied by this conjecture) was proved for large tournaments by Kühn–Osthus (2013), but that does not resolve the stronger Bang-Jensen–Yeo conjecture.

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

Conjecture. Every k-arc-strong tournament decomposes into k spanning strong digraphs.

Discussion

Conjecture 8 implies Kelly's conjecture ( Every regular tournament of order $ n $ can be decomposed into $ (n-1)/2 $ Hamilton directed cycles. ) which has been proved for tournaments of sufficiently large order by Kühn and Osthus [KO]. Bang-Jensen and Yeo [BY] gave several results supporting this conjecture. For example they proved it for $ k $ -arc-strong tournaments with minimum in- and out-degree at least $ 37k $ .

Bibliography

★ [BY] J. Bang-Jensen, A. Yeo, Decomposing k-arc-strong tournaments into strong spanning subdigraphs, Combinatorica 24 (2004) 331–349.
[KO] Daniela Kühn and Deryk Osthus, Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments, Advances in Mathematics 237 (2013), 62-146.