Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.12670 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912268854231040 |
|---|---|
| author | Garamvölgyi, Dániel Jordán, Tibor Király, Csaba Villányi, Soma |
| author_facet | Garamvölgyi, Dániel Jordán, Tibor Király, Csaba Villányi, Soma |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_12670 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Highly connected orientations from edge-disjoint rigid subgraphs Garamvölgyi, Dániel Jordán, Tibor Király, Csaba Villányi, Soma Combinatorics 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. |
| title | Highly connected orientations from edge-disjoint rigid subgraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.12670 |