Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Publication
Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
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 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.