Limits of degeneracy for colouring graphs with forbidden minors

Abstract

Motivated by Hadwiger's conjecture, Seymour asked which graphs $H$ have the property that every non-null graph $G$ with no $H$ minor has a vertex of degree at most $|V(H)|-2$. We show that for every monotone graph family $\mathcal{F}$ with strongly sublinear separators, all sufficiently large bipartite graphs $H\in \mathcal{F}$ with bounded maximum degree have this property. None of the conditions that $H$ belongs to $\mathcal{F}$, that $H$ is bipartite and that $H$ has bounded maximum degree can be omitted.

22 pages

References in corpus (3)

• Extremal density for sparse minors and subdivisions
• The extremal function for Petersen minors
• A lower bound on the average degree forcing a minor