• 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

The sandwich line-graph

Cornaz, Denis; Meurdesoif, Philippe (2010), The sandwich line-graph, Electronic Notes in Discrete Mathematics, 36, 1, p. 955-960. http://dx.doi.org/10.1016/j.endm.2010.05.121

View/Open
sandwich.PDF (73.37Kb)
sandwich_EN.PDF (163.2Kb)
Type
Article accepté pour publication ou publié
Date
2010
Journal name
Electronic Notes in Discrete Mathematics
Volume
36
Number
1
Publisher
Elsevier
Pages
955-960
Publication identifier
http://dx.doi.org/10.1016/j.endm.2010.05.121
Metadata
Show full item record
Author(s)
Cornaz, Denis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Meurdesoif, Philippe
Abstract (EN)
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
Subjects / Keywords
Lovász theta function; auxiliary line graph; Graph coloring

Related items

Showing items related by title and author.

  • Thumbnail
    A note on selective line-graphs and partition colorings 
    Cornaz, Denis; Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2019) Article accepté pour publication ou publié
  • Thumbnail
    Strengthening Lovász bound for coloring with a new graph transformation 
    Cornaz, Denis; Meurdesoif, Philippe (2012) Communication / Conférence
  • Thumbnail
    Packing and covering with linear programming: A survey. 
    Ries, Bernard; Cornaz, Denis; Bentz, Cédric (2013) Article accepté pour publication ou publié
  • Thumbnail
    Trader multiflow and box-TDI systems in series-parallel graphs 
    Cornaz, Denis; Grappe, Roland; Lacroix, Mathieu (2019) Article accepté pour publication ou publié
  • Thumbnail
    On minimal two-edge-connected graphs 
    Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha (2014) Communication / Conférence
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