Thumbnail - Request a copy

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
2012
Journal name
Discrete Mathematics
Volume
312
Number
10
Publisher
Elsevier
Pages
1838-1843
Publication identifier
Metadata
Show full item record
Author(s)
Zenklusen, Rico

de 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 graph