Article ID Journal Published Year Pages File Type
4648115 Discrete Mathematics 2012 6 Pages PDF
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
, , ,