A RELATIVE OF HADWIGER’S CONJECTURE

Abstract

Hadwiger’s conjecture asserts that if a simple graph G has no Kt+1 minor, then its vertex set V(G) can be partitioned into t stable sets. This is still open, but we prove under the same hypothesis that V(G) can be partitioned into t sets X-1, ..., X-t, such that for 1 <= i <= t, the subgraph induced on X-i has maximum degree at most a function of t. This is sharp, in that the conclusion becomes false if we ask for a partition into t - 1 sets with the same property.