• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

A note on chromatic properties of threshold graphs

Thumbnail
Date
2012
Dewey
Principes généraux des mathématiques
Sujet
Chromishold graphs; Chromatic number; Stable sets; Threshold values; Threshold graph
Journal issue
Discrete Mathematics
Volume
312
Number
10
Publication date
2012
Article pages
1838-1843
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.disc.2012.01.036
URI
https://basepub.dauphine.fr/handle/123456789/9745
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Zenklusen, Rico
status unknown
de Werra, Dominique
408616 Section de Mathématiques and Bernoulli Center, École Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland
Ries, Bernard
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Article accepté pour publication ou publié
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.