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
Section de Mathématiques and Bernoulli Center, École Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland
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é