Title of article :
A note on chromatic properties of threshold graphs
Author/Authors :
Ries، نويسنده , , Bernard and de Werra، نويسنده , , Dominique and Zenklusen، نويسنده , , Rico، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2012
Pages :
6
From page :
1838
To page :
1843
Abstract :
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.
Keywords :
Threshold values , chromatic number , Chromishold graphs , Threshold graph , Stable sets
Journal title :
Discrete Mathematics
Serial Year :
2012
Journal title :
Discrete Mathematics
Record number :
1599987
Link To Document :
بازگشت