CODeS research seminar: vertex coloring problem

Posted by: Reshma Chirayil Chandrasekharan
Date:2020-03-09
Contact:[email protected]

Dear colleagues and friends,

The CODeS research group is pleased to announce a seminar by Reshma Chirayil Chandrasekharan, KU Leuven, CODeS, entitled:

 The state of the art of the vertex coloring problem and a new constructive heuristic
Place: Room:A105, KU Leuven - Technologiecampus, Gebr. De Smetstraat 1, 9000 Gent
Date: 2020-03-19 
Time: 14.00
Abstract: The vertex colouring problem (VCP) is one of the most widely studied and popular problems in graph theory. The VCP seeks to assign colours to vertices of a graph such that no two adjacent vertices are assigned the same colour. Problems that require conflict resolution and partitioning mutually exclusive events such as scheduling, timetabling, puzzle solving and register allocation are broadly the areas where the VCP finds applications. Decades of research has contributed multiple models for the VCP. Despite these achievements, the problem continues to fascinate researchers in this area due to its theoretical complexity and the constantly growing number of practical applications that demand colouring larger graphs.

Determining the smallest number of colours required to colour a graph is proven to be an NP-hard problem. This in turn allows only graphs up to 100 vertices to be coloured by mathematical programming methods. However, practical applications concern colouring graphs ranging from thousands to millions of vertices, motivating the need of efficient heuristic strategies. The first part of the talk aims to discuss the state of the art of the VCP with a focus on heuristic approaches suitable for colouring medium to large graphs. During the second part, a novel heuristic approach that combines exact and heuristic approaches will be discussed.