Clique minors in graphs with a forbidden subgraph. Issue 3 (16th August 2021)

• Record Type: Journal Article
• Authors: Bucić, Matija; Fox, Jacob; Sudakov, Benny
• Is Part Of: Random structures & algorithms. Volume 60:Issue 3(2022)
• Page Start: 327
• Page End: 338
• Publication Date: 2021-08-16
• Subjects: graph minor -- Hadwiger conjecture -- H‐free graphs -- independent set expansion; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21038
• Languages: English
• ISSNs: 1042-9832

Abstract

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 α ( G ) at most r . If true Hadwiger's conjecture would imply the existence of a clique minor of order n / α ( G ) . Results of Kühn 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 Dvořák 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 Dvořák and Yepremyan. In particular, we show that any K s ‐free graph has a clique minor of order c s ( n / α ( G ) ) 1 + 1 10 ( s − 2 ), for some constant c s depending only on s . The exponent in this result is tight up to a constant factor in front of the 1 s − 2 term.