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

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