A BOUNDING ALGORITHM FOR SELECTIVE GRAPH COLORING PROBLEM (Development of Mathematical Optimization : Modeling and Algorithms)

Abstract

This note addresses the selective graph coloring problem, which is a generalization of the well-known vertex coloring problem. Given an undirected graph together with a partition of its vertex set, it is to find a subset of the vertex set which shares exactly one vertex with each component of the partition so that the chromatic number of the subgraph induced by the subset is minimum. In this note, we present a new column generation algorithm for a linear programming relaxation problem of the selective graph coloring.