Independence number in triangle-free graphs avoiding a minor

MaRDI QIDQ6322891zbMATH OpenFDO

Authors Zdeněk Dvořák, L. Yepremyan

Publication date 30 July 2019

Abstract: The celebrated Hadwiger's conjecture states that if a graph contains no $K_{t+1}$ minor then it is $t$-colourable. If true, it would in particular imply that every $n$-vertex $K_{t+1}$-minor-free graph has an independent set of size at least $n/t$. In 1982, Duchet and Meyniel proved that this bound holds within a factor $2$. Their bound has been improved; most notably in an absolute factor by Fox, which was later improved by Balogh and Kostochka. Here we consider the same question for triangle-free graphs. By the results of Shearer and Kostochka and Thomason, it follows that any triangle-free graph with no $K_t$ minor has an independent set of size $Omega(fracsqrtlogttn)$. We show that a much larger independent set exists; for all sufficiently large $t$ every triangle-free graph on $n$ vertices with no $K_t$-minor has an independent set of size $fracn{t}^{1-varepsilon}$. This answers a question of Sergey Norin.

This page was built for publication: Independence number in triangle-free graphs avoiding a minor

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