Decomposition of oriented k-partition-connected digraphs

From Egres Open
Jump to: navigation, search

Let D=(V,A) be a digraph whose underlying graph is k-partition-connected, and let [math]r_0 \in V[/math] be a node of in-degree 0. Suppose that the in-degree of every other node is at least k. Is it true that D can be decomposed into k weakly connected spanning subgraphs, so that every node [math]v \in V-r_0[/math] has positive in-degree in each subgraph?


Let [math]M_1[/math] be the cycle matroid of the underlying undirected graph of D, and let [math]M_2[/math] be the partition matroid where each class consists of the set of edges entering a given node [math]v \in V-r_0[/math]. The problem can be formulated as follows:

Is it true that if both [math]M_1[/math] and [math]M_2[/math] contain k disjoint spanning sets, then there are k disjoint common spanning sets?

This statement is known to be true for strongly base orderable matroids [1]; however, the cycle matroid of a graph is not necessarily base orderable.


  1. J. Davies, C. McDiarmid, Disjoint common transversals and exchange structures, Journal of the London Mathematical Society s2-14 (1976), 55-62. DOI link.