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

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

The sandwich line-graph

Thumbnail
Ouvrir
sandwich.PDF (73.37Kb)
sandwich_EN.PDF (163.2Kb)
Date
2010
Indexation documentaire
Principes généraux des mathématiques
Subject
Lovász theta function; auxiliary line graph; Graph coloring
Nom de la revue
Electronic Notes in Discrete Mathematics
Volume
36
Date de publication
08-2010
Pages article
955-960
Nom de l'éditeur
Elsevier
DOI
http://dx.doi.org/10.1016/j.endm.2010.05.121
URI
https://basepub.dauphine.fr/handle/123456789/5025
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Meurdesoif, Philippe
Cornaz, Denis
Type
Article accepté pour publication ou publié
Résumé en anglais
We observe that View the MathML source for any graph G with n vertices, where View the MathML source is any acyclic orientation of G and where View the MathML source is the (complement of the) auxiliary line graph introduced in [Cornaz, D., and Jost, V., A one-to-one correspondence between colorings and stable sets, Operations Research Letters 36 (2008), 673–676]. (Where as usual, ω and χ denote the clique number and the chromatic number.) It follows that, for any graph parameter β(G) sandwiched between ω(G) and χ(G), then View the MathML source is sandwiched between ω(G) and χ(G) too. Numerical experiments show that Φtheta is closer to χ than theta, where theta is Lovász theta function

  • 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

 Cette création est mise à disposition sous un contrat Creative Commons.