Highly connected orientations from edge-disjoint rigid subgraphs
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...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Cambridge University Press
2025-01-01
|
| Series: | Forum of Mathematics, Pi |
| Subjects: | |
| Online Access: | https://www.cambridge.org/core/product/identifier/S2050508625000046/type/journal_article |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850073571047505920 |
|---|---|
| author | Dániel Garamvölgyi Tibor Jordán Csaba Király Soma Villányi |
| author_facet | Dániel Garamvölgyi Tibor Jordán Csaba Király Soma Villányi |
| author_sort | Dániel Garamvölgyi |
| collection | DOAJ |
| description | 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 | Article |
| id | doaj-art-cd840968a37d47daaa2354f863927f93 |
| institution | DOAJ |
| issn | 2050-5086 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Cambridge University Press |
| record_format | Article |
| series | Forum of Mathematics, Pi |
| spelling | doaj-art-cd840968a37d47daaa2354f863927f932025-08-20T02:46:47ZengCambridge University PressForum of Mathematics, Pi2050-50862025-01-011310.1017/fmp.2025.4Highly connected orientations from edge-disjoint rigid subgraphsDániel Garamvölgyi0https://orcid.org/0000-0002-8468-6585Tibor Jordán1https://orcid.org/0000-0003-3662-5558Csaba Király2https://orcid.org/0000-0001-8081-9056Soma Villányi3https://orcid.org/0009-0009-9649-7077HUN-REN-ELTE Egerváry Research Group on Combinatorial Optimization, Pázmány Péter sétány 1/C, Budapest, 1117, Hungary; E-mail: HUN-REN Alfréd Rényi Institute of Mathematics, Reáltanoda utca 13-15, Budapest, 1053, Hungary; E-mail:HUN-REN-ELTE Egerváry Research Group on Combinatorial Optimization, Pázmány Péter sétány 1/C, Budapest, 1117, Hungary; E-mail: Department of Operations Research, Eötvös Loránd University, Pázmány Péter sétány 1/C, Budapest, 1117, Hungary; E-mail:HUN-REN-ELTE Egerváry Research Group on Combinatorial Optimization, Pázmány Péter sétány 1/C, Budapest, 1117, Hungary; E-mail:HUN-REN-ELTE Egerváry Research Group on Combinatorial Optimization, Pázmány Péter sétány 1/C, Budapest, 1117, Hungary; E-mail: Department of Operations Research, Eötvös Loránd University, Pázmány Péter sétány 1/C, Budapest, 1117, Hungary; E-mail: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.https://www.cambridge.org/core/product/identifier/S2050508625000046/type/journal_article05C4052C25 |
| spellingShingle | Dániel Garamvölgyi Tibor Jordán Csaba Király Soma Villányi Highly connected orientations from edge-disjoint rigid subgraphs Forum of Mathematics, Pi 05C40 52C25 |
| title | Highly connected orientations from edge-disjoint rigid subgraphs |
| title_full | Highly connected orientations from edge-disjoint rigid subgraphs |
| title_fullStr | Highly connected orientations from edge-disjoint rigid subgraphs |
| title_full_unstemmed | Highly connected orientations from edge-disjoint rigid subgraphs |
| title_short | Highly connected orientations from edge-disjoint rigid subgraphs |
| title_sort | highly connected orientations from edge disjoint rigid subgraphs |
| topic | 05C40 52C25 |
| url | https://www.cambridge.org/core/product/identifier/S2050508625000046/type/journal_article |
| work_keys_str_mv | AT danielgaramvolgyi highlyconnectedorientationsfromedgedisjointrigidsubgraphs AT tiborjordan highlyconnectedorientationsfromedgedisjointrigidsubgraphs AT csabakiraly highlyconnectedorientationsfromedgedisjointrigidsubgraphs AT somavillanyi highlyconnectedorientationsfromedgedisjointrigidsubgraphs |