Journal article

On the complexity of the selective graph coloring problem in some special classes of graphs

BP2-STS

Show more…
  • 2014
Published in:
  • Theoretical Computer Science. - Elsevier BV. - 2014, vol. 540-541, p. 89-102
English In this paper, we consider the selective graph coloring problem. Given an integer k ≥ 1
and a graph G = (V, E) with a partition V1, . . . , Vp of V, it consists in deciding whether
there exists a set V∗ in G such that |V∗ ∩ Vi| = 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.
Faculty
Faculté des sciences économiques et sociales et du management
Department
Département d'informatique
Language
  • English
Classification
Computer science and technology
License
Rights reserved
Open access status
green
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/325860
Statistics

Document views: 14 File downloads:
  • SELCOL_copy.pdf: 27