### Abstract

Original language | English |
---|---|

Journal | Journal of Combinatorial Theory. Series B |

Volume | 102 |

Issue number | 4 |

Pages (from-to) | 852-868 |

ISSN | 0095-8956 |

DOIs | |

Publication status | Published - 2012 |

### Keywords

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

### Cite this

*Journal of Combinatorial Theory. Series B*,

*102*(4), 852-868. https://doi.org/10.1016/j.jctb.2012.03.001

}

*Journal of Combinatorial Theory. Series B*, vol. 102, no. 4, pp. 852-868. https://doi.org/10.1016/j.jctb.2012.03.001

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

Research output: Contribution to journal › Journal article › Research › peer-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 -