|
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^5)$ 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.
Bibtex entry:
| AUTHOR | = | {Garamvölgyi, D{\'a}niel and Jord{\'a}n, Tibor and Kir{\'a}ly, Csaba and Vill{\'a}nyi, Soma}, |
| TITLE | = | {Highly connected orientations from edge-disjoint rigid subgraphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2024}, |
| NUMBER | = | {TR-2024-03} |