The graph coloring problem is a classic combinatorial problem that is known to be NP-hard. The running time of the fastest known algorithms (in the worst-case scenario) scales roughly as 2ⁿ, where n is number of vertices in the input graph.

The goal of  the pro gradu project is to review the recent algorithmic developments and implement the techniques into a state-of-the-art computer program. The program will be made freely available in the Internet.

Key reference:

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto: Covering and Packing in Linear Space. ICALP (1) 2010: 727-737