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

    Research output: Book/ReportReportResearchpeer-review


    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 aset inducing a $3$-degenerate graph.
    Original languageEnglish
    Number of pages8
    Publication statusPublished - 2000

    Cite this