• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

A note on chromatic properties of threshold graphs

Zenklusen, Rico; de Werra, Dominique; Ries, Bernard (2012), A note on chromatic properties of threshold graphs, Discrete Mathematics, 312, 10, p. 1838-1843. 10.1016/j.disc.2012.01.036

Type
Article accepté pour publication ou publié
Date
2012
Journal name
Discrete Mathematics
Volume
312
Number
10
Publisher
Elsevier
Pages
1838-1843
Publication identifier
10.1016/j.disc.2012.01.036
Metadata
Show full item record
Author(s)
Zenklusen, Rico

de Werra, Dominique
Section de Mathématiques and Bernoulli Center, École Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland
Ries, Bernard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
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 tp such that for any subset S of vertices the sum of the weights is at most tp 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.
Subjects / Keywords
Chromishold graphs; Chromatic number; Stable sets; Threshold values; Threshold graph

Related items

Showing items related by title and author.

  • Thumbnail
    Blockers and transversalsnext term in some previous termsubclasses of bipartite graphs: When caterpillars are dancing on a gridnext term 
    Bentz, Cédric; Costa, Marie-Christine; Ries, Bernard; de Werra, Dominique; Picouleau, Christophe; Zenklusen, Rico (2010) Article accepté pour publication ou publié
  • Thumbnail
    d-bloqueurs et d-transversaux 
    Bentz, Cédric; Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard; Zenklusen, R. (2009) Communication / Conférence
  • Thumbnail
    Bicolored matchings in some classes of graphs 
    Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard (2004) Article accepté pour publication ou publié
  • Thumbnail
    On the use of graphs in discrete tomography 
    de Werra, Dominique; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard (2010) Article accepté pour publication ou publié
  • Thumbnail
    d-Transversals of stable sets and vertex covers in weighted bipartite graphs 
    Bentz, Cédric; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard; de Werra, Dominique (2012) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo