Graph coloring as integer programs: an experimental comparison
Compare integer programming formulations of graph coloring on benchmark graphs.
- Suitable for
- Undergraduate thesis
- Supervision
- Tülay Ayyıldız
- Prerequisites
- Graph theory basics; programming
Graph coloring can be written as an integer linear program in several ways (assignment, representatives, set covering, …), and the choice of formulation strongly affects solver performance.
Goal
Implement several formulations with an open-source solver, run them on standard benchmark graphs, and explain the differences in running time and in the strength of their linear relaxations.