Back
1-s2.0-s1572528613000443-main
Journal article

Perfectness of clustered graphs

BP2-STS

Show more…
  • 2013
Published in:
  • Discrete Optimization. - Elsevier BV. - 2013, vol. 10, no. 4, p. 296-303
Applied Mathematics
Computational Theory and Mathematics
Theoretical Computer Science
Selective coloring
Partition coloring
Conformal matrix
Perfect matrix
Threshold graph
English Given a clustered graph (G,P), that is, a graph G = (V, E) together with a partition P of its vertex set, the selective coloring problem consists in choosing one vertex per cluster such that the chromatic number of the subgraph induced by the chosen vertices is minimum. This problem can be formulated as a covering problem with a 0–1 matrix M(G,P). Nevertheless, we observe that, given (G,P), it is NP-hard to check if M(G,P) is conformal (resp. perfect).We will give a sufficient condition, checkable in polynomial time, for M(G,P) to be conformal that becomes also necessary if conformality is required to be hereditary. Finally, we show that M(G,P) is perfect for every partition P if and only if G belongs to a superclass of threshold graphs defined with a complex function instead of a real one.
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
bronze
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/322637
Statistics
Document views: 35 File downloads:
  • 1-s2.0-s1572528613000443-main.pdf: 53