A polynomial time list colouring algorithm for series-parallel graphs

Given a graph and an assignment of lists to its nodes, a list colouring is an assignment of colours to the nodes of the graph, so that adjacent nodes receive different colours and each colour receives a colour from its list. The question is: given a particular graph and list assignment, does a list colouring exist? An algorithm is presented here that answers this question for series-parallel graphs. The algorithm has complexity O(md^2), where m is the number of edges, and d is the maximum degree of the graph. A necessary and sufficient condition for the existence of a list colouring is given, which is based on a recursively defined function. The analysis of the necessity of this condition leads to a set of valid inequalities for the list colouring polytope.