Linear-sized minors with given edge density

MaRDI QIDQ6403464zbMATH OpenFDO

Authors Tung H. Nguyen

Publication date 28 June 2022

Abstract: It is proved that for every $varepsilon>0$, there exists $K>0$ such that for every integer $tge2$, every graph with chromatic number at least $Kt$ contains a minor with $t$ vertices and edge density at least $1-varepsilon$. Indeed, building on recent work of Delcourt and Postle on linear Hadwiger's conjecture, for $varepsilonin(0,frac1256)$ we can take $K=Cloglog(1/varepsilon)$ where $C>0$ is a universal constant, which extends their recent $O(tloglogt)$ bound on the chromatic number of graphs with no $K_t$ minor.

This page was built for publication: Linear-sized minors with given edge density

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6403464)