1Departament de Matemàtica Aplicada II (Universitat Politècnica de Catalunya (UPC) Edifici Omega, Campus Nord Jordi Girona, 1-3 E-08034 Barcelona Spain - Espagne)
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.
https://hal.inria.fr/hal-00966507
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s
<>
Soumis le : mercredi 26 mars 2014 - 16:59:24
Dernière modification le : samedi 3 mars 2018 - 01:04:58
Document(s) archivé(s) le : jeudi 26 juin 2014 - 11:56:11
David R. Wood. Independent sets in graphs with an excluded clique minor. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (1), pp.171--175. 〈hal-00966507〉
