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.
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 |