A Note on Hadwiger's Conjecture

Abstract

Hadwiger's Conjecture states that every $K_{t+1}$-minor-free graph is $t$-colourable. It is widely considered to be one of the most important conjectures in graph theory. If every $K_{t+1}$-minor-free graph has minimum degree at most $\delta$, then every $K_{t+1}$-minor-free graph is $(\delta +1)$-colourable by a minimum-degree-greedy algorithm. The purpose of this note is to prove a slightly better upper bound.

References in corpus (1)

• On triangles in K_r-minor free graphs