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

    Cite this

    Kawarabayashi, Ken-ichi ; Thomassen, Carsten. / From the plane to higher surfaces. In: Journal of Combinatorial Theory. Series B. 2012 ; Vol. 102, No. 4. pp. 852-868.
    @article{369524df6a5a4ca89c568ad16f285d37,
    title = "From the plane to higher surfaces",
    abstract = "We show that Gr{\"o}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.",
    keywords = "Planar graphs, Higher surfaces, 3-colorability, List-coloring, Decomposition",
    author = "Ken-ichi Kawarabayashi and Carsten Thomassen",
    year = "2012",
    doi = "10.1016/j.jctb.2012.03.001",
    language = "English",
    volume = "102",
    pages = "852--868",
    journal = "Journal of Combinatorial Theory. Series B",
    issn = "0095-8956",
    publisher = "Academic Press",
    number = "4",

    }

    From the plane to higher surfaces. / Kawarabayashi, Ken-ichi; Thomassen, Carsten.

    In: Journal of Combinatorial Theory. Series B, Vol. 102, No. 4, 2012, p. 852-868.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - From the plane to higher surfaces

    AU - Kawarabayashi, Ken-ichi

    AU - Thomassen, Carsten

    PY - 2012

    Y1 - 2012

    N2 - 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.

    AB - 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.

    KW - Planar graphs

    KW - Higher surfaces

    KW - 3-colorability

    KW - List-coloring

    KW - Decomposition

    U2 - 10.1016/j.jctb.2012.03.001

    DO - 10.1016/j.jctb.2012.03.001

    M3 - Journal article

    VL - 102

    SP - 852

    EP - 868

    JO - Journal of Combinatorial Theory. Series B

    JF - Journal of Combinatorial Theory. Series B

    SN - 0095-8956

    IS - 4

    ER -