A Note on Hadwiger's Conjecture

2013/04/24 by Wood, David R.
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1304.6510

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 δ, then every K_t+1-minor-free graph is (δ+1)-colourable by a minimum-degree-greedy algorithm. The purpose of this note is to prove a slightly better upper bound.

Related

• Proof of the Clustered Hadwiger Conjecture
• Coloration of K₇^--minor free graphs
• Asymptotic Equivalence of Hadwiger's Conjecture and its Odd Minor-Variant
• Improved bound for Hadwiger's conjecture
• Further progress towards Hadwiger's conjecture