K5-subdivisions in Graphs

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    In 1964 Dirac conjectured that every graph with vertices and at least 3n-5 edges contains a subdivision of K5. We prove a weakened version with 7/2 n-7 instead of 3n-5. We prove that, for any prescribed vertex v0 the subdivision can be found such that v0 is not one of the five branch vertices. This variant of Dirac's problem, which was suggested by the present author in 1973, is best possible in the sense that 7/2 n -7 cannot be replaced by 7/2 n-15/2.
    Original languageEnglish
    JournalCombinatorics, Probability & Computing
    Volume5
    Issue number2
    Pages (from-to)179-189
    ISSN0963-5483
    DOIs
    Publication statusPublished - 1996

    Fingerprint

    Dive into the research topics of 'K5-subdivisions in Graphs'. Together they form a unique fingerprint.

    Cite this