News

Solution for a long-standing conjecture of Thomassen

A classical theorem of Nash-Williams implies that every $2k$-edge-connected graph has a $k$-arc-connected orientation. In 1985, Thomassen asked whether a similar statement is true for vertex-connectivity, and formulated a conjecture stating that for every positive integer $k$ there exists a smallest integer $f(k)$ such that every $f(k)$-connected graph has a $k$-connected orientation. In a recent paper titled Highly connected orientations from edge-disjoint rigid subgraphs, Garamvölgyi, Jordán, Király and Villányi answered this conjecture in the affirmative by proving that a connectivity of order $O(k^5)$ suffices. This is a beautiful and significant result, congratulations to the authors!