Color-critical graphs on a fixed surface
type: Item
instance of: scholarly article
title: Color-critical graphs on a fixed surface
zbMATH Open document ID: 0883.05051
author: Carsten Thomassen
published in: Journal of Combinatorial Theory. Series B
publication date: 1998-02-22T00:00:00Z
review text: A graph is \(k\)-color-critical if its vertex chromatic number is \(k\), but every proper subgraph is (\(k-1\))-colorable. It is known that for each orientable surface \(S\) and for each \(k \geq 7\), there are only finitely many \(k\)-color-critical graphs on \(S\). On the other hand, there are infinitely many 5-critical graphs on each surface \(S\) except the sphere. In this paper the author shows that for each orientable surface \(S\) there are only finitely many 6-color-critical graphs on \(S\). He also shows that if \(k \geq 5\), then there exists a polynomially-bounded algorithm for deciding if a graph on \(S\) can be \(k\)-colored. The techniques involve cutting the surface and graph to transform it into a planar graph, then applying various 5-coloring results for planar graphs. Some extensions of the results are given where a small subgraph is pre-colored, to list colorings, and to non-orientable surfaces.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1076872
zbMATH Keywords: chromatic number
zbMATH Keywords: surface
zbMATH Keywords: sphere
zbMATH Keywords: color-critical graphs
zbMATH Keywords: planar graph
zbMATH Keywords: colorings
reviewed by: Dan S. Archdeacon
MaRDI profile type: Publication
full work available at URL: jctb.1996.1722
OpenAlex ID: W1978313715
cites work: Locally Planar Toroidal Graphs are 5-Colorable
cites work: Q3688408
cites work: Additivity of the genus of a graph
cites work: Unsolved problems in geometry
cites work: The Colouring of Maps
cites work: Q3922703
cites work: Geometric coloring theory
cites work: The non-existence of colorings
cites work: Q5732334
cites work: Q4198056
cites work: Coloring graphs with fixed genus and girth
cites work: The complexity of planar graph choosability
cites work: Q4857375
cites work: Blocks and the nonorientable genus of graphs
cites work: Planarity and duality of finite and infinite graphs
cites work: Embeddings of graphs with no short noncontractible cycles
cites work: Five-coloring maps on surfaces
cites work: Five-coloring graphs on the torus
cites work: Every planar graph is 5-choosable
cites work: List colourings of planar graphs
DOI: 10.1006/JCTB.1996.1722
description: scientific article; zbMATH DE number 1076872