Ries, Bernardde Werra, DominiqueZenklusen, Rico2012-05-252012-05-252012-05-25201210.1016/j.disc.2012.01.036https://infoscience.epfl.ch/handle/20.500.14299/80761WOS:000303288500032In 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 t(p) such that for any subset S of vertices the sum of the weights is at most t(p) 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. (c) 2012 Elsevier B.V. All rights reserved.Threshold graphThreshold valuesStable setsChromatic numberChromishold graphstext::journal::journal article::research article