Linear-sized minors with given edge density

Tung H. Nguyen

Published 2022-06-28Version 1

It is proved that for every $\varepsilon>0$, there exists $c>0$ such that for every $t\ge2$, every graph with chromatic number at least $t$ contains a minor with at least $ct$ vertices and at most an $\varepsilon$ fraction of all possible edges missing. This is related to linear Hadwiger's conjecture.