[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