Finding dense minors using average degree
Abstract Motivated by Hadwiger's conjecture, we study the problem of finding the densest possible ‐vertex minor in graphs of average degree at least . We show that if has average degree at least , it contains a minor on vertices with at least edges. We show that this cannot be improved beyond . Finally, for we exactly determine the number of edges we are guaranteed to find in the densest ‐vertex minor in graphs of average degree at least .
Authors
- Sergey Norin (ORCID: https://orcid.org/0000-0003-4833-7983)
- Raphael Steiner (ORCID: https://orcid.org/0000-0002-4234-6136)
- Jérémie Turcotte (ORCID: https://orcid.org/0000-0002-4555-8425)
- Kevin Hendrey
Institutions
- ETH Zurich (CH)
- Institute for Basic Science (KR)
- McGill University (CA)
Publication Details
- Journal
- Journal of Graph Theory
- Published
- 2024-09-16
- DOI
- https://doi.org/10.1002/jgt.23169
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Institute for Basic Science
- Natural Sciences and Engineering Research Council of Canada