Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648115 | Discrete Mathematics | 2012 | 6 Pages |
Abstract
In threshold graphs one may find weights for the vertices and a threshold value tt such that for any subset SS of vertices, the sum of the weights is at most the threshold tt if and only if the set SS is a stable (independent) set. In this note we ask a similar question about vertex colorings: given an integer pp, when is it possible to find weights (in general depending on pp) for the vertices and a threshold value tptp such that for any subset SS of vertices the sum of the weights is at most tptp if and only if SS generates a subgraph with chromatic number at most p−1p−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 pp simultaneously.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Bernard Ries, Dominique de Werra, Rico Zenklusen,