3-Coloring graphs embedded in surfaces (Q4948508)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1429753
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | 3-Coloring graphs embedded in surfaces |
scientific article; zbMATH DE number 1429753 |
Statements
11 April 2000
0 references
3-coloring
0 references
vertex coloring
0 references
surface
0 references
3-Coloring graphs embedded in surfaces (English)
0 references
0.8783019781112671
0 references
0.8496126532554626
0 references
0.8446134328842163
0 references
0.8295071125030518
0 references
P. Erdős (1990) raised the following question which is a relaxation of R. Steinberg's conjecture: Is there an integer \(k\geq 5\) such that, if \(G\) is a planar graph without \(i\)-circuits, \(4\leq i\leq k\), then \(G\) is 3-colorable? In this paper, the author proves that for any surface \(\Sigma\), there exists an integer \(k(\Sigma)\geq 5\) such that, if \(G\) is a graph embedded in \(\Sigma\) without \(i\)-circuits, \(4\leq i\leq k(\Sigma)\), then \(G\) is 3-colorable. This result extends some earlier results on Erdős' question obtained by H. L. Abbott and B. Zhou (1991), D. P. Sanders and the author (1995) as well as O. V. Borodin (1996).
0 references
