On a conjecture of Thomassen (Q2517648)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a conjecture of Thomassen |
scientific article |
Statements
On a conjecture of Thomassen (English)
0 references
27 August 2015
0 references
Summary: In 1989, \textit{C. Thomassen} [in: Combinatorial mathematics, Proc. 3rd Int. Conf., New York/ NY (USA) 1985, Ann. N. Y. Acad. Sci. 555, 402--412 (1989; Zbl 0709.05030)] 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.
0 references
graph connectivity
0 references
digraphs
0 references
Thomassen
0 references