Originator: Michael Stiebitz (1995), Noga Alon (2006) (presented by Timothy Brauch - REGS 2007)
Definitions: Let d=(d1,...,dk). Given a list d, a d-splitting of an oriented graph G is a vertex partition V1,...,Vk such that each induced subdigraph G[Vi] has minimum outdegree at least di.
Question: Is it true that for every list d of positive integers, there is an integer r such that every oriented graph G with minimum outdegree at least r has a d-splitting? Let F(d) be the least such integer (when one exists), and write Fk(d) for F(d) when all di=d.
Comments/Partial results: Alon stated this as a problem in [A2], summarizing earlier work. He observed that Fk(1) is the minimum r such that every oriented graph with minimum outdegree at least r contains at least k pairwise disjoint cycles (after extracting cycles, the remaining vertices can be added to any vertex class in which they have a successor). Bermond and Thomassen [BT] conjectured that Fk(1)=2k-1. Thomassen [T] proved this for k≤2 and proved that Fk(1)≤(k+1)! in general. Alon [A1] proved a upper bound for Fk(1) that is linear in k and suggested that perhaps F(2,2) or even F(2,1) is not finite.
The undirected analogue is much simpler and was perhaps conjectured by Thomassen. Stiebitz [S] proved that δ(G)≥ -1+∑(d_i+1) implies that V(G) splits into sets V1,...,Vk such that δ(G[Vi]) ≥di for each i (this is sharp, using complete graphs). In this problem the case k=2 suffices for the general case. Splitting for a lower bound on δ(G) is more difficult than splitting to guarantee an upper bound on maximum degree [L], but it still fits on one page.
The night before this digraph question was presented in REGS, Stiebitz posed the digraph question in email intended as an open problem for the Research Problems from the CanaDAM conference. Stiebitz takes a far more optimistic view than Alon. He seems to think that the same value s+t+1 will suffice as F(s,t), but he no longer conjectures that value explicitly, instead merely asking whether F(s,t) exists. He also writes "The above question was first proposed by the author during the problem session of the Third Prague Midsummer Combinatorial Workshop held in Prague, August 20 - 24, 1995."
Indeed, André Kézdy constructed an example showing that F(2,2)>5.
References:
[A1] N. Alon, Disjoint directed cycles, J. Combin. Theory Ser. B 68 (1996), no. 2, 167-178.
[A2] N. Alon, Splitting digraphs, Combinatorics, Probability and Computing 15 (2006), 933-937.
[BT] J.-C. Bermond, C. Thomassen, Cycles in digraphs---a survey, J. Graph Theory 5 (1981), no. 1, 1-43.
[L] L. Lovasz, On decomposition of graphs, Studia Sci. Math. Hungar. 1 1966 237-238.
[S] M. Stiebitz, Decomposing graphs under degree constraints, J. Graph Theory 23 (1996), no. 3, 321-324.
[T] C. Thomassen, Even cycles in directed graphs, European J. Combin. 6 (1985), no. 1, 85-89.