Highly connected orientations from edge-disjoint rigid subgraphs

Abstract

We give an affirmative answer to a long-standing conjecture of Thomassen, stating that every sufficiently highly connected graph has a k-vertex-connected orientation. We prove that a connectivity of order $O(k^2)$ suffices. As a key tool, we show that for every pair of positive integers d and t, every $(t \cdot h(d))$ -connected graph contains t edge-disjoint d-rigid (in particular, d-connected) spanning subgraphs, where $h(d) = 10d(d+1)$ . This also implies a positive answer to the conjecture of Kriesell that every sufficiently highly connected graph G contains a spanning tree T such that $G-E(T)$ is k-connected.

Keywords

• 05C40
• 52C25