Arc-disjoint strongly connected spanning subdigraphs

Importance: Medium ✭✭
Subject: Graph Theory
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: March 2nd, 2013

\begin{conjecture} There exists an ineteger $k$ so that every $k$-arc-connected digraph contains a pair of arc-disjoint strongly connected spanning subdigraphs? \end{conjecture}

Bang-Jensen and Yeo [BY] proved the conjecture for several classes like tournaments. There is \OPrefnum[stronger conjecture for tournaments]{4765}. Yeo (See [BG, Theorem 13.10.1]) showed that it is NP-complete to decide whether a 2-regular digraph has two arc-disjoint strongly connected spanning subdigraphs.

A similar question can be asked about \OPrefnum[arc-disjoint out-branching and in-branching]{46495}. Several related problems are mentioned in the survey of Bang-Jensen and Kriesell [BK].

% 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

[BG] J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd. ed., Springer Verlag (2009).

[BK] J. Bang-Jensen, M. Kriesell, Disjoint sub(di)graphs in digraphs, Electronic Notes in Discrete Mathematics 34 (2009), 179-183.

*[BY] J. Bang-Jensen, A. Yeo, Decomposing k-arc-strong tournaments into strong spanning subdigraphs, Combinatorica 24 (2004), 331-349.

% 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.