A polynomial time list colouring algorithm for series-parallel graphs

Authors: 

Jeannette Janssen
Philippe Maheux

Author Addresses: 

Jeannette Janssen (janssen@mathstat.dal.ca)
Philippe Maheux (maheux@cs.dal.ca)
Dept. of Mathematics and Statistics
Dalhousie University
B3H 3J5 Halifax, NS

Abstract: 

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.

Tech Report Number: 
CS-2002-02
Report Date: 
April 30, 2002
AttachmentSize
PDF icon CS-2002-02.pdf242.85 KB