[Dept. of Computer Science]

Experimentation Project ACS

Title	Computing the edge chromatic number of a graph
Student	Vacant
Supervisor	Han Hoogeveen, Marjan van den Akker
ECTS	7.5 or 15
Related Course(s)	Scheduling and Timetabling, Algorithms and Networks
Description	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 each edge gets colored edges that have a vertex in common must get a different color. The minimum number of colors needed is called the edge chromatic number of a graph; it is well-known that the chromatic number is either equal to the maximum degree or the maximum degree plus 1. 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.
Special Note