7-critical graphs of bounded genus (Q1210575)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: 7-critical graphs of bounded genus |
scientific article; zbMATH DE number 179607
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | 7-critical graphs of bounded genus |
scientific article; zbMATH DE number 179607 |
Statements
7-critical graphs of bounded genus (English)
0 references
30 August 1993
0 references
For each compact surface \(\Sigma\), the author shows that (a) there exists only a finite number of vertex critical 7-colourable graphs which can be embedded in \(\Sigma\), and (b) there exists a polynomial time algorithm to test if a graph, which can be embedded in \(\Sigma\), has chromatic number \(\geq 7\).
0 references
bounded genus
0 references
critical graph
0 references
Euler's formula
0 references
chromatic number
0 references
