The complexity of some graph colouring problems (Q1192946)

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.