
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
Type
Article accepté pour publication ou publiéDate
2010Journal name
Electronic Notes in Discrete MathematicsVolume
36Number
1Publisher
Elsevier
Pages
955-960
Publication identifier
Metadata
Show full item recordAuthor(s)
Cornaz, DenisLaboratoire 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 functionSubjects / Keywords
Lovász theta function; auxiliary line graph; Graph coloringRelated items
Showing items related by title and author.
-
Cornaz, Denis; Furini, Fabio; Malaguti, Enrico; Santini, Alberto (2019) Article accepté pour publication ou publié
-
Cornaz, Denis; Meurdesoif, Philippe (2012) Communication / Conférence
-
Ries, Bernard; Cornaz, Denis; Bentz, Cédric (2013) Article accepté pour publication ou publié
-
Cornaz, Denis; Grappe, Roland; Lacroix, Mathieu (2019) Article accepté pour publication ou publié
-
Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha (2014) Communication / Conférence