• 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