Thumbnail

Selective Graph Coloring in Some Special Classes of Graphs

Ries, Bernard; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2012), Selective Graph Coloring in Some Special Classes of Graphs, in Paschos, Vangelis Th.; Milis, Ioannis; Markakis, Vangelis; Mahjoub, A. Ridha, Combinatorial Optimization, Springer, p. 320-331. 10.1007/978-3-642-32147-4_29

View/Open
Type
Communication / Conférence
Date
2012
Conference title
ISCO 2012
Conference date
2012-05
Conference city
Athènes
Conference country
Greece
Book title
Combinatorial Optimization
Book author
Paschos, Vangelis Th.; Milis, Ioannis; Markakis, Vangelis; Mahjoub, A. Ridha
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
7422/2012
ISBN
978-3-642-32146-7
Pages
320-331
Publication identifier
Metadata
Show full item record
Author(s)
Ries, Bernard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Pop, Petrica

Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Demange, Marc
ESSEC Business School
Abstract (EN)
In this paper, we consider the selective graph coloring problem. Given an integer k ≥ 1 and a graph G = (V,E) with a partition V 1,…,V p of V, it consists in deciding whether there exists a set V * in G such that |V * ∩ V i | = 1 for all i ∈ {1,…,p}, and such that the graph induced by V * is k-colorable. We investigate the complexity status of this problem in various classes of graphs.
Subjects / Keywords
complete q-partite graphs; split graphs; bipartite graphs; scheduling; computational complexity