Clique minors in graphs with a forbidden subgraph

Matija Bucić, Jacob Fox, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

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 (Formula presented.) at most r. If true Hadwiger's conjecture would imply the existence of a clique minor of order (Formula presented.). 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 (Formula presented.) -free graph has a clique minor of order (Formula presented.), for some constant (Formula presented.) depending only on s. The exponent in this result is tight up to a constant factor in front of the (Formula presented.) term.

Original languageEnglish (US)
Pages (from-to)327-338
Number of pages12
JournalRandom Structures and Algorithms
Volume60
Issue number3
DOIs
StatePublished - May 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Keywords

  • graph minor
  • H-free graphs
  • Hadwiger conjecture
  • independent set expansion

Fingerprint

Dive into the research topics of 'Clique minors in graphs with a forbidden subgraph'. Together they form a unique fingerprint.

Cite this