Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

Independent sets in graphs with an excluded clique minor

Abstract : Let G be a graph with n vertices, with independence number α, and with no Kt+1-minor for some t ≥ 5. It is proved that (2α - 1)(2t - 5) ≥ 2n - 5. This improves upon the previous best bound whenever n≥2/5t2.
Document type :
Journal articles
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-00966507
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Wednesday, March 26, 2014 - 4:59:24 PM
Last modification on : Monday, November 16, 2020 - 3:56:03 PM
Long-term archiving on: : Thursday, June 26, 2014 - 11:56:11 AM

File

617-2510-1-PB.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

David R. Wood. Independent sets in graphs with an excluded clique minor. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, Vol. 9 no. 1 (1), pp.171--175. ⟨10.46298/dmtcs.385⟩. ⟨hal-00966507⟩

Share

Metrics

Record views

34

Files downloads

641