id: 06039238
dt: j
an: 06039238
au: Ries, Bernard; De Werra, Dominique; Zenklusen, Rico
ti: A note on chromatic properties of threshold graphs.
so: Discrete Math. 312, No. 10, 1838-1843 (2012).
py: 2012
pu: Elsevier Science B.V. (North-Holland), Amsterdam
la: EN
cc: 
ut: threshold graph; threshold values; stable sets; chromatic number;
    chromishold graphs
ci: 
li: doi:10.1016/j.disc.2012.01.036
ab: Summary: 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.
rv: