• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Perfectness of clustered graphs

Thumbnail
View/Open
6ded79080bcd840f83243706e2a3fb28515e.pdf (346.4Kb)
Date
2013
Dewey
Principes généraux des mathématiques
Sujet
Threshold graph; Perfect matrix; Conformal matrix; Partition coloring; Selective coloring
Journal issue
Discrete Optimization
Volume
10
Number
4
Publication date
2013
Article pages
296-303
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.disopt.2013.07.006
URI
https://basepub.dauphine.fr/handle/123456789/11973
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Ries, Bernard
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ekim, Tinaz
Cornaz, Denis
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Bonomo, Flavia
193425 University of Buenos Aires
Type
Article accepté pour publication ou publié
Abstract (EN)
Given a clustered graph (G,V), that is, a graph G=(V,E) together with a partition V 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,V). Nevertheless, we observe that, given (G,V), it is NP-hard to check if M(G,V) is conformal (resp. perfect). We will give a sufficient condition, checkable in polynomial time, for M(G,V) to be conformal that becomes also necessary if conformality is required to be hereditary. Finally, we show that M(G,V) is perfect for every partition V if and only if G belongs to a superclass of threshold graphs defined with a complex function instead of a real one.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.