From the plane to higher surfaces

Ken-ichi Kawarabayashi, Carsten Thomassen

    Research output: Contribution to journalJournal articleResearchpeer-review

    1 Downloads (Pure)

    Abstract

    We show that Grötzschʼs theorem extends to all higher surfaces in the sense that every triangle-free graph on a surface of Euler genus g becomes 3-colorable after deleting a set of at most 1000⋅g⋅f(g) vertices where f(g) is the smallest edge-width which guarantees a graph of Euler genus g and girth 5 to be 3-colorable.We derive this result from a general cutting technique which we also use to extend other results on planar graphs to higher surfaces in the same spirit, even after deleting only 1000g vertices. These include the 5-list-color theorem, results on arboricity, and various types of colorings, and decomposition theorems of planar graphs into two graphs with prescribed degeneracy properties.It is not known if the 4-color theorem extends in this way.
    Original languageEnglish
    JournalJournal of Combinatorial Theory. Series B
    Volume102
    Issue number4
    Pages (from-to)852-868
    ISSN0095-8956
    DOIs
    Publication statusPublished - 2012

    Keywords

    • Planar graphs
    • Higher surfaces
    • 3-colorability
    • List-coloring
    • Decomposition

    Fingerprint Dive into the research topics of 'From the plane to higher surfaces'. Together they form a unique fingerprint.

    Cite this