Decomposing a planar graph into an independent set and a 3-degenerate graph

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    We prove the conjecture made by O. V. Borodin in 1976 that the vertex set of every planar graph can be decomposed into an independent set and a set inducing a 3-degenerate graph. (C) 2001 Academic Press.
    Original languageEnglish
    JournalJournal of Combinatorial Theory. Series B
    Volume83
    Issue number2
    Pages (from-to)262-271
    ISSN0095-8956
    DOIs
    Publication statusPublished - Nov 2001

    Fingerprint

    Dive into the research topics of 'Decomposing a planar graph into an independent set and a 3-degenerate graph'. Together they form a unique fingerprint.

    Cite this