Back
Document
Journal article

On some applications of the selective graph coloring problem

    2015
Published in:
  • European Journal of Operational Research. - 2015, vol. 240, no. 2, p. 307-314
combinatorial optimization
graph theory
partition colouring
selective colouring
computational complexity
English In this paper we present the Selective Graph Coloring Problem, a generalization of the standard graph col-oring 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 dif-ferent 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.
Faculty
Faculté des sciences économiques et sociales et du management
Department
Département d'informatique
Language
  • English
Classification
Computer science and technology
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/308608
Statistics
Document views: 106 File downloads:
  • Document: 1192