• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2015
Journal name
European Journal of Operational Research
Volume
240
Number
2
Publisher
Elsevier
Pages
307-314
Publication identifier
10.1016/j.ejor.2014.05.011
Metadata
Show full item record
Author(s)
Demange, Marc
ESSEC 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 complexity

Related items

Showing items related by title and author.

  • Thumbnail
    On the complexity of the selective graph coloring problem in some special classes of graphs 
    Ries, Bernard; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2014) Article accepté pour publication ou publié
  • Thumbnail
    Selective Graph Coloring in Some Special Classes of Graphs 
    Ries, Bernard; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2012) Communication / Conférence
  • Thumbnail
    Efficient recognition of equimatchable graphs 
    Ekim, Tinaz; Demange, Marc (2014) Article accepté pour publication ou publié
  • Thumbnail
    Perfectness of clustered graphs 
    Ries, Bernard; Ekim, Tinaz; Cornaz, Denis; Bonomo, Flavia (2013) Article accepté pour publication ou publié
  • Thumbnail
    Split-critical and uniquely split-colorable graphs 
    Ekim, Tinaz; Ries, Bernard; de Werra, Dominique (2010) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo