How hard is it to list-colour the edges of a graph?
Jeannette Janssen
Dalhousie University
janssen@mathstat.dal.ca
Given a graph, and a list of colours for each edge, a (edge)
list-colouring is an assignment of a colours to each edge such that
incident edges receive different colours, and each edge receives a colour
from its list. Finding a list-colouring must be a hard problem, since
graph colouring is know to be hard in general. However, for bipartite
graphs and certain other classes of graphs, edge colouring is easy.
Moreover, Galvin proved in 1994 that for bipartite graphs the
list-chromatic index (the minimum list size such that a list colouring
can
always be found) equals the chromatic index (the minimum number of
colours
needed to colour the edges). However, even if the list-chromatic index of
a graph is known, the question remains whether a list-colouring can be
found given a particular set of lists. This talk will explore the
fronteer
between hard and easy for this problem. We will give an
overview of hardness results, and discuss ways to approach
list-colouring algorithms.
CONE MAY 2000