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
    0 references
    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
    0 references
    graph connectivity
    0 references
    digraphs
    0 references
    Thomassen
    0 references
    0 references