Importance: Medium ✭✭
 Author(s): Bang-Jensen, Joergen Yeo, Anders
 Subject: Graph Theory » Directed Graphs » » Tournaments
 Keywords:
 Posted by: fhavet on: March 15th, 2013

\begin{conjecture} Every k-arc-strong tournament decomposes into k spanning strong digraphs. \end{conjecture}

Conjecture 8 implies Kelly's conjecture (\emph{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$.

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

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.

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

* indicates original appearance(s) of problem.