On some applications of the selective graph coloring problem
Demange, Marc; Ekim, Tinaz; Ries, Bernard; Tanasescu, Cerasela (2015), On some applications of the selective graph coloring problem, European Journal of Operational Research, 240, 2, p. 307-314. 10.1016/j.ejor.2014.05.011
Type
Article accepté pour publication ou publiéDate
2015Journal name
European Journal of Operational ResearchVolume
240Number
2Publisher
Elsevier
Pages
307-314
Publication identifier
Metadata
Show full item recordAuthor(s)
Demange, MarcESSEC Business School
Ekim, Tinaz
Industrial Engineering Department [Istanbul]
Ries, Bernard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Tanasescu, Cerasela
ESSEC Business School
Abstract (EN)
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 – some already discussed in previous papers and some new ones – 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.Subjects / Keywords
Combinatorial optimization; Graph theory; Partition coloring; Selective coloring; Computational complexityRelated items
Showing items related by title and author.
-
Ries, Bernard; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2014) Article accepté pour publication ou publié
-
Ries, Bernard; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2012) Communication / Conférence
-
Ekim, Tinaz; Demange, Marc (2014) Article accepté pour publication ou publié
-
Ries, Bernard; Ekim, Tinaz; Cornaz, Denis; Bonomo, Flavia (2013) Article accepté pour publication ou publié
-
Ekim, Tinaz; Ries, Bernard; de Werra, Dominique (2010) Article accepté pour publication ou publié