|Title||Computing the edge chromatic number of a graph|
|Supervisor||Han Hoogeveen, Marjan van den Akker|
|ECTS||7.5 or 15|
|Related Course(s)||Scheduling and Timetabling, Algorithms and Networks|
Consider a given graph G=(V,E), where V is the set of vertices and
E is the set of edges. The goal is to color the edges of the graph
with as few colors as possible, such that
Since each set of edges with equal color corresponds to a matching, the problem can be reformulated to: partition the edge set in as few matchings as possible.
The goal of the project is to solve the above problem using column generation.