Perfectness of clustered graphs
BP2STS
Published in:
 Discrete Optimization.  Elsevier BV.  2013, vol. 10, no. 4, p. 296303
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 NPhard 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


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: 13
File downloads:
 1s2.0s1572528613000443main.pdf: 19