Cyril Grelier

New Bounds and Constraint Programming Models for the Weighted Vertex Coloring Problem

This paper addresses the weighted vertex coloring problem (WVCP) which is an NP-hard variant of the graph coloring problem with various applications. Given a vertex-weighted graph, the problem consists of partitioning vertices in independent sets (colors) so as to minimize the sum of the maximum we…