Premium
A decomposition approach to solve the selective graph coloring problem in some perfect graph families
Author(s) -
Şeker Oylum,
Ekim Tınaz,
Taşkın Z. Caner
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21850
Subject(s) - combinatorics , chordal graph , graph coloring , fractional coloring , mathematics , greedy coloring , edge coloring , list coloring , complete coloring , discrete mathematics , split graph , graph power , neighbourhood (mathematics) , pathwidth , graph , line graph , 1 planar graph , mathematical analysis
Graph coloring is the problem of assigning a minimum number of colors to all vertices of a graph such that no two adjacent vertices receive the same color. The selective graph coloring problem is a generalization of the standard graph coloring problem; given a graph with a partition of its vertex set into clusters, the objective is to choose exactly one vertex per cluster so that, among all possible selections, the number of colors necessary to color the vertices in the selection is minimum. This study focuses on a decomposition based exact solution framework for selective coloring in some perfect graph families: in particular, permutation, generalized split, and chordal graphs where the selective coloring problem is known to be NP‐hard. Our method combines integer programming techniques and combinatorial algorithms for the graph classes of interest. We test our method on graphs with different sizes and densities, present computational results and compare them with solving an integer programming formulation of the problem by CPLEX, and a state‐of‐the art algorithm from the literature. Our computational experiments indicate that our decomposition approach significantly improves solution performance in low‐density graphs, and regardless of edge‐density in the class of chordal graphs.