@article {1431,
	title = {A decomposition approach to solve the selective graph coloring problem in some perfect graph families},
	journal = {Networks},
	volume = {73},
	year = {2019},
	pages = {145-169},
	abstract = {<p>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.</p>},
	keywords = {chordal graphs, decomposition algorithm, generalized split graphs, integer programming, partition coloring, permutation graphs, selective graph coloring},
	doi = {https://doi.org/10.1002/net.21850},
	url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/net.21850},
	author = {{\c S}eker, Oylum and Ekim, Tinaz and Z C Ta{\c s}k{\i}n}
}
@article {1511,
	title = {On some applications of the selective graph coloring problem},
	journal = {European Journal of Operational Research},
	volume = {240},
	year = {2015},
	pages = {307-314},
	abstract = {<p>In this paper we present the Selective Graph Coloring Problem, a generalization of the standard graph coloring problem as well as several of its possible applications. Given a graph with a partition of its vertex set into several clusters, we want to select one vertex per cluster such that the chromatic number of the subgraph induced by the selected vertices is minimum. This problem appeared in the literature under different names for specific models and its complexity has recently been studied for different classes of graphs. Here, we describe different models {\textendash} some already discussed in previous papers and some new ones {\textendash} in very different contexts under a unified framework based on this graph problem. We point out similarities between these models, offering a new approach to solve them, and show some generic situations where the selective graph coloring problem may be used. We focus on specific graph classes motivated by each model, and we briefly discuss the complexity of the selective graph coloring problem in each one of these graph classes and point out interesting future research directions.</p>},
	keywords = {Combinatorial optimization, Computational complexity, Graph theory, partition coloring, Selective coloring},
	issn = {0377-2217},
	doi = {https://doi.org/10.1016/j.ejor.2014.05.011},
	url = {https://www.sciencedirect.com/science/article/pii/S0377221714004184},
	author = {Marc Demange and Ekim, Tinaz and Bernard Ries and Cerasela Tanasescu}
}
