Totally odd K-4-subdivisions in 4-chromatic graphs

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    We prove the conjecture made by Bjarne Toft in 1975 that every 4-chromatic graph contains a subdivision of K-4 in which each edge of K-4 corresponds to a path of odd length. As an auxiliary result we characterize completely the subspace of the cycle space generated by all cycles through two fixed edges. Toft's conjecture was proved independently in 1995 by Wenan Zang.
    Original languageEnglish
    JournalCombinatorica
    Volume21
    Issue number3
    Pages (from-to)217-443
    ISSN0209-9683
    DOIs
    Publication statusPublished - 2001

    Fingerprint Dive into the research topics of 'Totally odd K-4-subdivisions in 4-chromatic graphs'. Together they form a unique fingerprint.

    Cite this