Three-coloring graphs embedded on surfaces with all faces even-sided
type: Item
instance of: scholarly article
title: Three-coloring graphs embedded on surfaces with all faces even-sided
zbMATH Open document ID: 0828.05029
author: Joan P. Hutchinson
published in: Journal of Combinatorial Theory. Series B
publication date: 1995-09-20T00:00:00Z
review text: Every graph embedded on a surface of positive genus with every face bounded by an even number of edges can be 3-colored provided all noncontractible cycles in the graph are sufficiently long. The bound of three colors is the smallest possible for this type of result.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 798761
zbMATH Keywords: plane
zbMATH Keywords: planar graphs
zbMATH Keywords: Heawood's bound
zbMATH Keywords: embedding
zbMATH Keywords: torus
zbMATH Keywords: toroidal graph
zbMATH Keywords: graph embedded on a surface
zbMATH Keywords: positive genus
zbMATH Keywords: noncontractible cycles
zbMATH Keywords: bound
zbMATH Keywords: three colors
MaRDI profile type: Publication
full work available at URL: jctb.1995.1047
OpenAlex ID: W1990994902
DOI: 10.1006/JCTB.1995.1047
Recommended article: 3-Coloring graphs embedded in surfaces
Recommended article: 3-colorable even embeddings on closed surfaces
Recommended article: On the Total Coloring of Graphs Embeddable in Surfaces
Recommended article: Q5206906
Recommended article: 3-regular colored graphs and classification of surfaces
Recommended article: 3-Regular Non 3-Edge-Colorable Graphs with Polyhedral Embeddings in Orientable Surfaces
Recommended article: Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies
Recommended article: Q4633818
Recommended article: Coloring Triangle-Free Graphs on Surfaces
Recommended article: Three-coloring triangle-free graphs on surfaces. III. Graphs of girth five
description: scientific article; zbMATH DE number 798761