Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Independent sets in ...
Article

Independent sets in graphs with an excluded clique minor

David R. Wood ORCID (1)
(1) Departament de Matemàtica Aplicada II
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2007
Last modified on
March 31, 2025
Volume 9
vol. 9:1
Graph and Algorithms
DOI
10.46298/dmtcs.385
License
https://about.hal.science/hal-authorisation-v1
Indicators
867
Views
648
Downloads

Independent sets in graphs with an excluded clique minor

David R. Wood ORCID (1)
(1) Departament de Matemàtica Aplicada II
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Cited by

Source: OpenCitations

  • Large minors in graphs with given independence number

    Discrete Mathematics

    Authors : József Balogh, A.V. Kostochka ORCID

    Journal reference : Volume 311, 2011, pp. 2203-2215

    DOI : 10.1016/j.disc.2011.07.003

  • Clique immersions and independence number

    arXiv (Cornell University)

    Authors : Sebastián Bustamante, Daniel A. Quiroz ORCID, Maya Stein ORCID, José Zamora ORCID

    Journal reference : Volume 106, 2022, pp. 103550

    DOI : 10.1016/j.ejc.2022.103550

  • Biclique immersions in graphs with independence number 2

    Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications

    Authors : Fábio Botler ORCID, Andrea Jiménez ORCID, Carla Lintzmayer ORCID, Adrián Pastine ORCID, Daniel Quiroz ORCID, Maycon Sambinelli ORCID

    Journal reference : Volume , 2023, pp. 169-177

    DOI : 10.5817/cz.muni.eurocomb23-024
Preview
Loading PDF preview...