Clique minors in graphs with a forbidden subgraph
METADATA ONLY
Loading...
Author / Producer
Date
2022-05
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
The classical Hadwiger conjecture dating back to 1940s states that any graph of chromatic number at least r has the clique of order r as a minor. Hadwiger's conjecture is an example of a well-studied class of problems asking how large a clique minor one can guarantee in a graph with certain restrictions. One problem of this type asks what is the largest size of a clique minor in a graph on n vertices of independence number alpha(G) at most r. If true Hadwiger's conjecture would imply the existence of a clique minor of order n/alpha(G). Results of Kuhn and Osthus and Krivelevich and Sudakov imply that if one assumes in addition that G is H-free for some bipartite graph H then one can find a polynomially larger clique minor. This has recently been extended to triangle-free graphs by Dvorak and Yepremyan, answering a question of Norin. We complete the picture and show that the same is true for arbitrary graph H, answering a question of Dvorak and Yepremyan. In particular, we show that any Ks-free graph has a clique minor of order cs(n/alpha(G))1+110(s-2), for some constant cs depending only on s. The exponent in this result is tight up to a constant factor in front of the 1s-2 term.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
60 (3)
Pages / Article No.
327 - 338
Publisher
Wiley
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
graph minor; Hadwiger conjecture; H-free graphs; independent set expansion
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
Notes
Funding
196965 - Problems in Extremal and Probabilistic Combinatorics (SNF)