A note on chromatic properties of threshold graphs
Zenklusen, Rico; de Werra, Dominique; Ries, Bernard (2012), A note on chromatic properties of threshold graphs, Discrete Mathematics, 312, 10, p. 1838-1843. 10.1016/j.disc.2012.01.036
Type
Article accepté pour publication ou publiéDate
2012Journal name
Discrete MathematicsVolume
312Number
10Publisher
Elsevier
Pages
1838-1843
Publication identifier
Metadata
Show full item recordAuthor(s)
Zenklusen, Ricode Werra, Dominique
Ries, Bernard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
In threshold graphs one may find weights for the vertices and a threshold value t such that for any subset S of vertices, the sum of the weights is at most the threshold t if and only if the set S is a stable (independent) set. In this note we ask a similar question about vertex colorings: given an integer p, when is it possible to find weights (in general depending on p) for the vertices and a threshold value tp such that for any subset S of vertices the sum of the weights is at most tp if and only if S generates a subgraph with chromatic number at most p−1? We show that threshold graphs do have this property and we show that one can even find weights which are valid for all values of p simultaneously.Subjects / Keywords
Chromishold graphs; Chromatic number; Stable sets; Threshold values; Threshold graphRelated items
Showing items related by title and author.
-
Bentz, Cédric; Costa, Marie-Christine; Ries, Bernard; de Werra, Dominique; Picouleau, Christophe; Zenklusen, Rico (2010) Article accepté pour publication ou publié
-
Bentz, Cédric; Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard; Zenklusen, R. (2009) Communication / Conférence
-
Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard (2004) Article accepté pour publication ou publié
-
de Werra, Dominique; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard (2010) Article accepté pour publication ou publié
-
Bentz, Cédric; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard; de Werra, Dominique (2012) Article accepté pour publication ou publié