Geodesic
Highly connected orientations from edge-disjoint rigid subgraphs
Forum of Mathematics, Pi, Tome 13 (2025) no. 1, p. e11

Voir la notice de l'article provenant de la source Cambridge University Press

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. 
Garamvölgyi, Dániel; Jordán, Tibor; Király, Csaba; Villányi, Soma. Highly connected orientations from edge-disjoint rigid subgraphs. Forum of Mathematics, Pi, Tome 13 (2025) no. 1, p. e11. doi: 10.1017/fmp.2025.4
@article{10_1017_fmp_2025_4,
     author = {Garamv\"olgyi, D\'aniel and Jord\'an, Tibor and Kir\'aly, Csaba and Vill\'anyi, Soma},
     title = {Highly connected orientations from edge-disjoint rigid subgraphs},
     journal = {Forum of Mathematics, Pi},
     pages = {e11},
     year = {2025},
     volume = {13},
     number = {1},
     doi = {10.1017/fmp.2025.4},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fmp.2025.4/}
}
TY  - JOUR
AU  - Garamvölgyi, Dániel
AU  - Jordán, Tibor
AU  - Király, Csaba
AU  - Villányi, Soma
TI  - Highly connected orientations from edge-disjoint rigid subgraphs
JO  - Forum of Mathematics, Pi
PY  - 2025
SP  - e11
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fmp.2025.4/
DO  - 10.1017/fmp.2025.4
ID  - 10_1017_fmp_2025_4
ER  - 
%0 Journal Article
%A Garamvölgyi, Dániel
%A Jordán, Tibor
%A Király, Csaba
%A Villányi, Soma
%T Highly connected orientations from edge-disjoint rigid subgraphs
%J Forum of Mathematics, Pi
%D 2025
%P e11
%V 13
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1017/fmp.2025.4/
%R 10.1017/fmp.2025.4
%F 10_1017_fmp_2025_4

[1] Alon, N. and Spencer, J. H., The Probabilistic Method (Wiley-Interscience series in discrete mathematics and optimization), third edn. (Hoboken, NJ, Wiley, 2008). Google Scholar | DOI

[2] Cheriyan, J., Durand De Gevigney, O. and Szigeti, Z., ‘Packing of rigid spanning subgraphs and spanning trees’, J. Combin. Theory Ser. B 105 (2014), 17–25. Google Scholar | DOI

[3] Durand De Gevigney, O., ‘On Frank’s conjecture on -connected orientations’, J. Combin. Theory Ser. B 141 2020), 105–114. Google Scholar | DOI

[4] Frank, A., Connections in Combinatorial Optimization. Oxford Lecture Series in Mathematics and its Applications, 38 (Oxford University Press, Oxford, 2011). Google Scholar

[5] Frank, A., ‘Connectivity and network flows’, in Handbook of Combinatorics (Vol. 1) (Cambridge, MA, MIT Press, 1996), 111–177. Google Scholar

[6] Garamvölgyi, D., Jordán, T. and Király, Cs., ‘Count and cofactor matroids of highly connected graphs’, J. Combin. Theory Ser. B 166 (2024), 1–29. doi: 10.1016/j.jctb.2023.12.004. Google Scholar | DOI

[7] Graver, J. E., ‘Rigidity matroids’, SIAM J. Discrete Math. 4(3) (1991), 355–368. doi: 10.1137/0404032. Google Scholar | DOI

[8] Hakimi, S., ‘On the degrees of the vertices of a directed graph’, J. Franklin Instit. 279(4) (1965), 290–308. doi: 10.1016/0016-0032(65)90340-6. Google Scholar | DOI

[9] Jordán, T., ‘On the existence of k edge-disjoint 2-connected spanning subgraphs’, J. Combin. Theory Ser. B 95(2) (2005), 257–262. doi: 10.1016/j.jctb.2005.04.003. Google Scholar | DOI

[10] Kawarabayashi, K., Lee, O., Reed, B. and Wollan, P., ‘A weaker version of Lovász’ path removal conjecture’, J. Combin. Theory Ser. B 98(5) (2008), 972–979. Google Scholar | DOI

[11] Lovász, L. and Yemini, Y., ‘On generic rigidity in the plane’, SIAM J. Algebr. Discrete Meth. 3(1) (1982), 91–98. doi: 10.1137/0603009. Google Scholar | DOI

[12] Mohar, B., Nowakowski, R. J. and West, D. B., ‘Research problems from the 5th Slovenian Conference (Bled, 2003)’, Discrete Math. 307(3–5) (2007), 650–658. doi: 10.1016/j.disc.2006.07.013. Google Scholar | DOI

[13] St, C.. Nash-Williams, J. A., ‘Edge-disjoint spanning trees of finite graphs’, J. Lond. Math. Soc. (1) (1961), 445–450. Google Scholar

[14] Nguyen, V.-H., ‘On abstract rigidity matroids’, SIAM J. Discrete Math. 24(2) (2010), 363–369. doi: 10.1137/090762051. Google Scholar | DOI

[15] Oxley, J. G., Matroid Theory (Oxford Graduate Texts in Mathematics) vol. 21, second edn. (Oxford, NY, Oxford University Press, 2011). Google Scholar | DOI

[16] Robbins, H. E., ‘A theorem on graphs, with an application to a problem of traffic control’, Amer. Math. Monthly 46(5) (1939), 281. Google Scholar | DOI

[17] Schulze, B. and Whiteley, W., ‘Rigidity and scene analysis,’ in Handbook of Discrete and Computational Geometry, third edn. (CRC Press, Boca Raton, FL, 2017), 1565–1604. doi: 10.1201/9781315119601. Google Scholar

[18] Thomassen, C., ‘Configurations in graphs of large minimum degree, connectivity, or chromatic number’, Ann. New York Acad. Sci. 555(1) (1989), 402–412. doi: 10.1111/j.1749-6632.1989.tb22479.x. Google Scholar | DOI

[19] Thomassen, C., ‘Strongly 2-connected orientations of graphs’, J. Combin. Theory Ser. B 110 (2015), 67–78. Google Scholar | DOI

[20] Tutte, W. T., ‘On the problem of decomposing a graph into connected factors’, J. Lond. Math. Soc. (1) (1961), 221–230. doi: 10.1112/jlms/s1-36.1.221. Google Scholar | DOI

[21] Villányi, S., ‘Every -connected graph is globally rigid in ’, in J. Combin. Theory Ser. B. 173 (2025), 1–13. Google Scholar | DOI

[22] Whiteley, W., ‘Some matroids from discrete applied geometry’, in Bonin, J. E., Oxley, J. G. and Servatius, B. (Eds), Contemporary Mathematics vol. 197 (Providence, RI, American Mathematical Society, 1996), 171–311. doi: 10.1090/conm/197/02540. Google Scholar

Cité par Sources :