The complexity of some graph colouring problems (Q1192946)
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 61819
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The complexity of some graph colouring problems |
scientific article; zbMATH DE number 61819 |
Statements
The complexity of some graph colouring problems (English)
0 references
27 September 1992
0 references
This paper deals with the following two problems. The first is on the complexity of counting colourings of a degree fixed graph. The author shows that provided the maximum degree and the number of colours are both allowed to be at least 3, then counting the number of colours is \(\#P\)- complete even if the graph is restricted to be regular and bipratite. The second is on the colourability of graphs on fixed surfaces. The author establishes a linear time algorithm for determining the \(k\)-colourability of a graph on a fixed surface for \(k\geq 6\) fixed.
0 references
computing complexity
0 references
graph colouring
0 references
surface
0 references
linear time algorithm
0 references
0.8415976762771606
0 references
0.8316524624824524
0 references
0.8224144577980042
0 references
0.8224144577980042
0 references
