On a Conjecture of Thomassen

Michelle Delcourt, Asaf Ferber

Abstract


In 1989, Thomassen asked whether there is an integer-valued function $f(k)$ such that every $f(k)$-connected graph admits a spanning, bipartite $k$-connected subgraph. In this paper we take a first, humble approach, showing the conjecture is true up to a $\log n$ factor.


Keywords


Graph connectivity, digraphs, Thomassen

Full Text: PDF