From the plane to higher surfaces

Publication: Research - peer-reviewJournal article – Annual report year: 2012

View graph of relations

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
Publication date2012
Volume102
Issue4
Pages852-868
ISSN0095-8956
DOIs
StatePublished
CitationsWeb of Science® Times Cited: 1

Keywords

  • Planar graphs, Higher surfaces, 3-colorability, List-coloring, Decomposition
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 9739478